On b b -colorings in regular graphs ?
A b 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. El-Sahili and Kouider have conjectured that every d d -regular graph with girth at least 5 has a b b -coloring with d+1 d + 1 colors. We show that the Petersen graph infirms this conjecture, and we propose a new formulation of this question and give a positive answer for small degree.
coloration b b -coloring b b b b b a a -chromatic number a a a a a b b -chromatic number b b b b b