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.

Full text (pdf)

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