On bb-colorings in regular graphs

A bb-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 dd-regular graph with girth at least 5 has a bb-coloring with d+1d+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.