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. El-Sahili and Kouider have conjectured that every d-regular graph with girth at least 5 has a b-coloring with 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.
展开▼
