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

Mais Alkhateeb; Anja Kohl

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 4, page 709-735
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Mais Alkhateeb, and Anja Kohl. "Upper bounds on the b-chromatic number and results for restricted graph classes." Discussiones Mathematicae Graph Theory 31.4 (2011): 709-735. <http://eudml.org/doc/271042>.

@article{MaisAlkhateeb2011,
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.},
author = {Mais Alkhateeb, Anja Kohl},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {coloring; b-coloring; b-chromatic number; b-continuity; -coloring; -chromatic number; -continuity},
language = {eng},
number = {4},
pages = {709-735},
title = {Upper bounds on the b-chromatic number and results for restricted graph classes},
url = {http://eudml.org/doc/271042},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Mais Alkhateeb
AU - Anja Kohl
TI - Upper bounds on the b-chromatic number and results for restricted graph classes
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 4
SP - 709
EP - 735
AB - 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.
LA - eng
KW - coloring; b-coloring; b-chromatic number; b-continuity; -coloring; -chromatic number; -continuity
UR - http://eudml.org/doc/271042
ER -

References

top
  1. [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. Zbl1132.05020
  2. [2] T. Faik and J.-F. Sacle, Some b-continuous classes of graphs, Technical Report N1350, LRI (Universite de Paris Sud, 2003). 
  3. [3] J.L. Gross and J. Yellen, Handbook of Graph Theory (CRC Press, 2004). Zbl1036.05001
  4. [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. Zbl1092.05023
  5. [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. Zbl0933.05051
  6. [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. [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. [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. Zbl1008.05056
  9. [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. Zbl1087.05023
  10. [10] L. Rabern, A note on Reed's conjecture, SIAM J. Discrete Math. 22 (2008) 820-827, doi: 10.1137/060659193. Zbl1191.05042
  11. [11] S. Radziszowski, Small Ramsey Numbers, Electronic Journal of Combinatorics, Dynamic Survey DS1 (2006). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.