Opuscula Math. 33, no. 1 (2013), 19-28
http://dx.doi.org/10.7494/OpMath.2013.33.1.19

Opuscula Mathematica

# 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.

Full text (pdf)

• 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
• Revised: 2012-03-08.
• Accepted: 2012-09-18.