Opuscula Math. 33, no. 1 (2013), 19-28
On vertex b-critical trees
Mostafa Blidia
Noureddine Ikhlef Eschouf
Frédéric Maffray
Abstract.
A b-coloring is a proper coloring of the vertices of a graph such that each color class has a vertex that has neighbors of all other colors. The b-chromatic number of a graph \(G\) is the largest \(k\) such that \(G\) admits a b-coloring with \(k\) colors. A graph \(G\) is b-critical if the removal of any vertex of \(G\) decreases the b-chromatic number. We prove various properties of b-critical trees. In particular, we characterize b-critical trees.
Keywords:
b-coloring, b-critical graphs, b-critical trees.
Mathematics Subject Classification:
05C15.
About the authors ▼
Mostafa Blidia
University of Blida, LAMDA-RO, Department of Mathematics, B.P. 270, Blida, Algeria
Noureddine Ikhlef Eschouf
Dr. Yahia Fares University of Médéa, Faculty of Science and Technology, Department of G.E.I., Algeria
Frédéric Maffray
Grenoble-INP, Université Joseph Fourier, C.N.R.S, Laboratoire G-SCOP, Grenoble, France
About the article ▼
Received: 2011-05-09.
Revised: 2012-03-08.
Accepted: 2012-09-18.
Cite this article as ▼
Mostafa Blidia, Noureddine Ikhlef Eschouf, Frédéric Maffray, On vertex b-critical trees, Opuscula Math. 33, no. 1 (2013), 19-28,
http://dx.doi.org/10.7494/OpMath.2013.33.1.19.
Download this article's citation as: