DMGT

Discussiones Mathematicae Graph Theory 31(4) (2011) 709-735
DOI: https://doi.org/10.7151/dmgt.1575

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

Mais Alkhateeb

Faculty of Mathematics and Computer Science
TU Bergakademie Freiberg
09596 Freiberg, Germany

Anja Kohl

Faculty of Mathematics and Computer Science
TU Bergakademie Freiberg
09596 Freiberg, Germany

Abstract

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.

Keywords: coloring, b-coloring, b-chromatic number, b-continuity

2010 Mathematics Subject Classification: 05C15, 05C78.

References

[1]	D. Barth, J. Cohen and T. Faik, On the b-continuity property of graphs, Discrete Appl. Math. 155 (2007) 1761--1768, doi: 10.1016/j.dam.2007.04.011.
[2]	T. Faik and J.-F. Sacle, Some b-continuous classes of graphs, Technical Report N1350, LRI (Universite de Paris Sud, 2003).
[3]	J.L. Gross and J. Yellen, Handbook of Graph Theory (CRC Press, 2004).
[4]	C.T. Hoang and M. Kouider, On the b-dominating coloring of graphs, Discrete Appl. Math. 152 (2005) 176--186, doi: 10.1016/j.dam.2005.04.001.
[5]	R.W. Irving and D.F. Manlove, The b-chromatic number of a graph, Discrete Appl. Math. 91 (1999) 127--141, doi: 10.1016/S0166-218X(98)00146-2.
[6]	J. Kará, J. Kratochvil and M. Voigt, b-continuity, Preprint No. M 14/04, Technical University Ilmenau, Faculty for Mathematics and Natural Sciences (2004).
[7]	A. Kohl and I. Schiermeyer, Some Results on Reed's Conjecture about ω, Δ, and χ with respect to α, Discrete Math. 310 (2010) 1429--1438, doi: 10.1016/j.disc.2009.05.025.
[8]	M. Kouider and M. Maheo, Some bounds for the b-chromatic number of a graph, Discrete Math. 256 (2002) 267--277, doi: 10.1016/S0012-365X(01)00469-1.
[9]	M. Kouider and M. Zaker, Bounds for the b-chromatic number of some families of graphs, Discrete Math. 306 (2006) 617--623, doi: 10.1016/j.disc.2006.01.012.
[10]	L. Rabern, A note on Reed's conjecture, SIAM J. Discrete Math. 22 (2008) 820--827, doi: 10.1137/060659193 .
[11]	S. Radziszowski, Small Ramsey Numbers, Electronic Journal of Combinatorics, Dynamic Survey DS1 (2006).

Received 15 April 2010
Revised 9 November 2010
Accepted 11 November 2010