On b-vertex and b-edge critical graphs

• Autorzy: Eschouf N. I. , Blidia M.

Identyfikatory

DOI

http://dx.doi.Org/10.7494/OpMath.2015.35.2.171

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

b-coloring; b-chromatic number; critical graphs

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2015
• Tom: Vol. 35, no. 2
• Strony: 171--180
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Eschouf N. I.

• University Yahia Fares of Medea, Algeria

autor

Blidia M.

• University of Blida LAMDA-RO, Department of Mathematics B.R 270, Blida, Algeria

Bibliografia

• [1] C. Berge, Graphs, North Holland, 1985.
• [2] F. Bonomo, G. Duran, F. Maffray, J. Marenco, M. Valencia-Pabon, On the b-coloring of cographs and Pa-sparse graphs, Graphs and Combinatorics 25 (2009), 153-167.
• [3] M. Blidia, N. Ikhlel Eschoul, F. Maffray, b-coloring of some bipartite graphs, Aus­tralasian 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. Hoang, 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, Aus­tralasian Journal of Combinatorics 47 (2010), 21-35.
• [14] R.W. Irving, D.F. Manlove, The b-chromatic number of graphs, Discrete Applied Math­ematics 91 (1999), 127-141.
• [15] M. Jakovac, S. Klavzar, The b-chromatic number of cubic graphs, Graphs and Combi­natorics 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. Maheo, 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. Kratochvil, 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 olthe Computing Science Department ol Glasgow University, 1998.
• [22] S. Shaebani, On the b-chromatic number of regular graphs without Ą-cycle, arXiv: 1103.152 vi [math.CO] 08 Mar 2011.
• [23] S. Shaebani, The b-chromatic number of regular graphs via the edge connectivity, arXiv:1105.2909 vi [math.CO] 14 May 2011.
• [24] J. Ramirez-Alfonsin, B. Reed, Perfect Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, 2001.