Browsing by Subject "b-coloring"

Now showing 1 - 2 of 2

Access status: Open Access ,
On b-vertex and b-edge critical graphs
(2015) Eschouf, Noureddine Ikhlef; Blidia, Mostafa
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.
Access status: Open Access ,
On vertex b-critical trees
(2013) Blidia, Mostafa; Eschouf, Noureddine Ikhlef; Maffray, Frédéric
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.