Opuscula Mathematica
Opuscula Math. 35, no. 2 (2015), 171-180

On b-vertex and b-edge critical graphs

Noureddine Ikhlef Eschouf
Mostafa Blidia
Abstract. A \(b\)-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the \(b\)-chromatic number \(b(G)\) of a graph \(G\) is the largest integer \(k\) such that \(G\) admits a \(b\)-coloring with \(k\) colors. A simple graph \(G\) is called \(b^{+}\)-vertex (edge) critical if the removal of any vertex (edge) of \(G\) increases its \(b\)-chromatic number. In this note, we explain some properties in \(b^{+}\)-vertex (edge) critical graphs, and we conclude with two open problems.
Keywords: \(b\)-coloring, \(b\)-chromatic number, critical graphs.
Mathematics Subject Classification: 05C15.
Full text (pdf)
References ▼
  1. [1] C. Berge, Graphs, North Holland, 1985.
  2. [2] F. Bonomo, G. Durán, F. Maffray, J. Marenco, M. Valencia-Pabon, On the \(b\)-coloring of cographs and \(P_4\)-sparse graphs, Graphs and Combinatorics 25 (2009), 153-167.
  3. [3] M. Blidia, N. Ikhlef Eschouf, F. Maffray, \(b\)-coloring of some bipartite graphs, Australasian Journal of Combinatorics 53 (2012), 67-76.
  4. [4] M. Blidia, N. Ikhlef Eschouf, F. Maffray, On vertex \(b\)-critical trees, Opuscula Math. 33 (2013) 1, 19-28.
  5. [5] M. Blidia, N. Ikhlef Eschouf, F. Maffray, On edge-\(b\)-critical graphs, submitted to Discrete Applied Mathematics.
  6. [6] M. Blidia, F. Maffray, Z. Zemir, On \(b\)-colorings in regular graphs, Discrete Applied Mathematics 157 (2009), 1787-1793.
  7. [7] V. Compos, C. Linhares, F. Maffray, A. Sliva, \(b\)-chromatic number of Cacti, Electronic Notes in Discrete Mathematics 35 (2009), 281-286.
  8. [8] S. Cabello, M. Jakovac, On the \(b\)-chromatic number of regular graphs, Discrete Applied Mathematics 159 (2011) 13, 1303-1310.
  9. [9] T. Faik, About the \(b\)-continuity of graphs, Electronic Notes in Discrete Mathematics 17 (2004), 151-156.
  10. [10] A. El Sahili, M. Kouider, About \(b\)-colorings of regular graphs, Res. Rep. 1432, LRI, Univ. Orsay, France, 2006.
  11. [11] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics 57, 2nd ed., North Holland, 2004.
  12. [12] C.T. Hoàng, M. Kouider, On the \(b\)-dominating coloring of graphs, Discrete Applied Mathematics 152 (2005), 176-186.
  13. [13] N. Ikhlef Eschouf, Characterization of some \(b\)-chromatic edge critical graphs, Australasian Journal of Combinatorics 47 (2010), 21-35.
  14. [14] R.W. Irving, D.F. Manlove, The \(b\)-chromatic number of graphs, Discrete Applied Mathematics 91 (1999), 127-141.
  15. [15] M. Jakovac, S. Klavžar, The \(b\)-chromatic number of cubic graphs, Graphs and Combinatorics 26 (2010), 107-118.
  16. [16] R. Javadi, B. Omoomi, On \(b\)-coloring of cartesian product of graphs, to appear in Ars Combinatoria.
  17. [17] M. Kouider, \(b\)-chromatic number of a graph, subgraphs and degrees Rapport interne LRI 1392, Univ. Orsay, France, 2004.
  18. [18] M. Kouider, M. Mahéo, Some bounds for the \(b\)-chromatic number of a graph, Discrete Mathematics 256 (2002), 267-277.
  19. [19] M. Kouider, M. Zaker, Bounds for the \(b\)-chromatic number of some families of graphs, Discrete Mathematics 306 (2006) 7, 617-623.
  20. [20] J. Kratochvíl, Z. Tuza, M. Voigt, On the \(b\)-chromatic number of graphs, Lecture Notes in Computer Science 2573 (2002), 310-320.
  21. [21] D.F. Manlove, Minimaximal and maximinimal optimization problems: a partial order-based approach, PhD thesis, technical report tr-1998-27 of the Computing Science Department of Glasgow University, 1998.
  22. [22] S. Shaebani, On The \(b\)-chromatic number of regular graphs without 4-cycle, arXiv: 1103.152 v1 [math.CO] 08 Mar 2011.
  23. [23] S. Shaebani, The \(b\)-chromatic number of regular graphs via the edge connectivity, arXiv: 1105.2909 v1 [math.CO] 14 May 2011.
  24. [24] J. Ramirez-Alfonsin, B. Reed, Perfect Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, 2001.
About the authors ▼
Noureddine Ikhlef Eschouf
University Yahia Farès of Medéa, Algeria
Mostafa Blidia
University of Blida, LAMDA-RO, Department of Mathematics, B.P. 270, Blida, Algeria
About the article ▼
Communicated by Mariusz Meszka.
Received: 2013-10-07.
Revised: 2014-03-04.
Accepted: 2014-07-04.
Published online: 2014-11-18.
Cite this article as ▼
Noureddine Ikhlef Eschouf, Mostafa Blidia, On b-vertex and b-edge critical graphs, Opuscula Math. 35, no. 2 (2015), 171-180, http://dx.doi.org/10.7494/OpMath.2015.35.2.171.
Download this article's citation as: