Opuscula Math. 35, no. 2 (2015), 171-180
http://dx.doi.org/10.7494/OpMath.2015.35.2.171
Opuscula Mathematica
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.
- C. Berge, Graphs, North Holland, 1985.
- 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.
- M. Blidia, N. Ikhlef Eschouf, F. Maffray, \(b\)-coloring of some bipartite graphs, Australasian Journal of Combinatorics 53 (2012), 67-76.
- M. Blidia, N. Ikhlef Eschouf, F. Maffray, On vertex \(b\)-critical trees, Opuscula Math. 33 (2013) 1, 19-28.
- M. Blidia, N. Ikhlef Eschouf, F. Maffray, On edge-\(b\)-critical graphs, submitted to Discrete Applied Mathematics.
- M. Blidia, F. Maffray, Z. Zemir, On \(b\)-colorings in regular graphs, Discrete Applied Mathematics 157 (2009), 1787-1793.
- V. Compos, C. Linhares, F. Maffray, A. Sliva, \(b\)-chromatic number of Cacti, Electronic Notes in Discrete Mathematics 35 (2009), 281-286.
- S. Cabello, M. Jakovac, On the \(b\)-chromatic number of regular graphs, Discrete Applied Mathematics 159 (2011) 13, 1303-1310.
- T. Faik, About the \(b\)-continuity of graphs, Electronic Notes in Discrete Mathematics 17 (2004), 151-156.
- A. El Sahili, M. Kouider, About \(b\)-colorings of regular graphs, Res. Rep. 1432, LRI, Univ. Orsay, France, 2006.
- M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics 57, 2nd ed., North Holland, 2004.
- C.T. Hoàng, M. Kouider, On the \(b\)-dominating coloring of graphs, Discrete Applied Mathematics 152 (2005), 176-186.
- N. Ikhlef Eschouf, Characterization of some \(b\)-chromatic edge critical graphs, Australasian Journal of Combinatorics 47 (2010), 21-35.
- R.W. Irving, D.F. Manlove, The \(b\)-chromatic number of graphs, Discrete Applied Mathematics 91 (1999), 127-141.
- M. Jakovac, S. Klavžar, The \(b\)-chromatic number of cubic graphs, Graphs and Combinatorics 26 (2010), 107-118.
- R. Javadi, B. Omoomi, On \(b\)-coloring of cartesian product of graphs, to appear in Ars Combinatoria.
- M. Kouider, \(b\)-chromatic number of a graph, subgraphs and degrees Rapport interne LRI 1392, Univ. Orsay, France, 2004.
- M. Kouider, M. Mahéo, Some bounds for the \(b\)-chromatic number of a graph, Discrete Mathematics 256 (2002), 267-277.
- M. Kouider, M. Zaker, Bounds for the \(b\)-chromatic number of some families of graphs, Discrete Mathematics 306 (2006) 7, 617-623.
- J. Kratochvíl, Z. Tuza, M. Voigt, On the \(b\)-chromatic number of graphs, Lecture Notes in Computer Science 2573 (2002), 310-320.
- 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.
- S. Shaebani, On The \(b\)-chromatic number of regular graphs without 4-cycle, arXiv: 1103.152 v1 [math.CO] 08 Mar 2011.
- S. Shaebani, The \(b\)-chromatic number of regular graphs via the edge connectivity, arXiv: 1105.2909 v1 [math.CO] 14 May 2011.
- J. Ramirez-Alfonsin, B. Reed, Perfect Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, 2001.
- 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
- Communicated by Mariusz Meszka.
- Received: 2013-10-07.
- Revised: 2014-03-04.
- Accepted: 2014-07-04.
- Published online: 2014-11-18.
