From b-Coloring to b*-Coloring: Large Girth and Parameterized Complexity
Abstract
A b-coloring is a proper vertex coloring such that every color class contains a vertex, a so-called b-vertex, which sees all colors in its closed neighborhood. This type of coloring has been intensively studied from both structural and algorithmic point of view. Recently, Zaker [DAM 2025] introduced the notion of a b*-coloring, which is a b-coloring in which there is a vertex that sees a b-vertex of every color in its closed neighborhood. The b*-chromatic number is the maximum integer k such that there is a b*-coloring with k colors. We partially answer a question posed by Zaker and prove that graphs of girth at least 7 are b*-monotonic, which means that the b*-chromatic number does not increase by taking an induced subgraph. In addition, we discover a class of d-regular graphs of girth at least 5 with b*-chromatic number d+1, which strengthens a result about b-colorings by Dettlaff, Furmańczyk, Peterin, Roux, and Ziemann [AMC 2024]. We also study the parameterized complexity of finding b*-colorings, and show that for many structural parameters, the complexity coincides with that of finding b-colorings. In particular, the b*-chromatic number can be computed in polynomial time on any class of bounded clique-width. For most parameters, the translation from b-colorings is straightforward but for the feedback edge number, the FPT algorithm for b*-colorings is actually much simpler than that for b-colorings by Balabán [MFCS 2026].
Related
- On the Classical and Parameterized Complexity of Strong Odd Coloring
- Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number
- On the structure of graphs with given odd girth and large algebraic connectivity
- Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
- Computational complexity of the H-coloring problem in cubic graphs
BibTeX
@misc{balaban2026from,
title = {{From b-Coloring to $b^*$-Coloring: Large Girth and Parameterized Complexity}},
author = {Jakub Balabán and Oliver Bukor},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.03819},
eprint = {2608.03819},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.03819},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - From b-Coloring to b^*-Coloring: Large Girth and Parameterized Complexity
AU - Jakub Balabán
AU - Oliver Bukor
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.03819
UR - https://arxiv.org/abs/2608.03819
AB - A b-coloring is a proper vertex coloring such that every color class contains a vertex, a so-called b-vertex, which sees all colors in its closed neighborhood. This type of coloring has been intensively studied from both structural and algorithmic point of view. Recently, Zaker [DAM 2025] introduced the notion of a b*-coloring, which is a b-coloring in which there is a vertex that sees a b-vertex of every color in its closed neighborhood. The b*-chromatic number is the maximum integer k such that there is a b*-coloring with k colors. We partially answer a question posed by Zaker and prove that graphs of girth at least 7 are b*-monotonic, which means that the b*-chromatic number does not increase by taking an induced subgraph. In addition, we discover a class of d-regular graphs of girth at least 5 with b*-chromatic number d+1, which strengthens a result about b-colorings by Dettlaff, Furmańczyk, Peterin, Roux, and Ziemann [AMC 2024]. We also study the parameterized complexity of finding b*-colorings, and show that for many structural parameters, the complexity coincides with that of finding b-colorings. In particular, the b*-chromatic number can be computed in polynomial time on any class of bounded clique-width. For most parameters, the translation from b-colorings is straightforward but for the feedback edge number, the FPT algorithm for b*-colorings is actually much simpler than that for b-colorings by Balabán [MFCS 2026].
ER -