Upper bounds on the b-chromatic number and results for restricted graph classes

A b-coloring of a graph G by k colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k−1 color classes. The b-chromatic number χb(G) is the maximum integer k for which G has a b-coloring by k colors. Moreover, the graph G is called b-continuous if G admits a b-coloring by k colors for all k satisfying χ(G) ≤ k ≤ χb(G). In this paper, we establish four general upper bounds on χb(G). We present results on the b-chromatic number and the b-continuity problem for special graphs, in particular for disconnected graphs and graphs with independence number 2. Moreover we determine χb(G) for graphs G with minimum degree δ(G) ≥ |V (G)| − 3, graphs G with clique number ω(G) ≥ |V (G)| − 3, and graphs G with independence number α(G) ≥ |V (G)| − 2. We also prove that these graphs are b-continuous.