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)

• 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
• Revised: 2014-03-04.
• Accepted: 2014-07-04.