Improved bounds on the b-chromatic number using the independence and chromatic numbers
Abstract
Finding a minimum proper vertex coloring is NP-hard and hard to approximate. B-coloring is used as a heuristic approach to graph coloring. A b-coloring of a graph G is a proper vertex coloring where each color class contains at least one vertex (a b-vertex) adjacent to a vertex in every other color class. The maximum number of colors in such a coloring is the b-chromatic number, b(G). A b∗-coloring is a variation in which a b-vertex is adjacent to a b-vertex in every other color class. We employ the b∗-coloring to prove that any n-vertex graph G with independence number at most t satisfies b(G) ≤ [(t−1)n+tχ(G)]/(2t−1). This bound extends the bounds of Kouider and Zaker (2006) and Alkhateeb and Kohl (2011) and significantly improves the bound in terms of the clique partition number. We show that this bound is sharp for all t≥ 2 and χ(G)≥ 3. Furthermore, we provide a refined bound based on the maximum number of vertex-disjoint independent sets of size t. Finally, we prove b∗(G) ≤ [(t−2)n+(t−1)χ(G)]/(2t−3) for all K1,t-free graphs G, a significant improvement over the analogous bound for b(G).
Related
- Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
- Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers
- An improved upper bound on the chromatic number of the n-dimensional sphere
- Explicit and logarithmically improved chromatic bounds for (P2∪ P3)-free graphs
- Bounds on the maximum denominator of fractional chromatic numbers
BibTeX
@misc{zaker2026improved,
title = {{Improved bounds on the b-chromatic number using the independence and chromatic numbers}},
author = {Manouchehr Zaker},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.07461},
eprint = {2606.07461},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.07461},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Improved bounds on the b-chromatic number using the independence and chromatic numbers
AU - Manouchehr Zaker
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2606.07461
UR - https://arxiv.org/abs/2606.07461
AB - Finding a minimum proper vertex coloring is NP-hard and hard to approximate. B-coloring is used as a heuristic approach to graph coloring. A b-coloring of a graph G is a proper vertex coloring where each color class contains at least one vertex (a b-vertex) adjacent to a vertex in every other color class. The maximum number of colors in such a coloring is the b-chromatic number, b(G). A b^∗-coloring is a variation in which a b-vertex is adjacent to a b-vertex in every other color class. We employ the b^∗-coloring to prove that any n-vertex graph G with independence number at most t satisfies b(G) ≤ [(t−1)n+tχ(G)]/(2t−1). This bound extends the bounds of Kouider and Zaker (2006) and Alkhateeb and Kohl (2011) and significantly improves the bound in terms of the clique partition number. We show that this bound is sharp for all t≥ 2 and χ(G)≥ 3. Furthermore, we provide a refined bound based on the maximum number of vertex-disjoint independent sets of size t. Finally, we prove b^∗(G) ≤ [(t−2)n+(t−1)χ(G)]/(2t−3) for all K_1,t-free graphs G, a significant improvement over the analogous bound for b(G).
ER -