On the bb-chromatic number of regular bounded graphs

A bb-coloring of a graph is a proper coloring such that every color class contains a vertex adjacent to at least one vertex in each of the other color classes. The bb-chromatic number of a graph GG, denoted by b(G)b(G), is the maximum integer kk such that GG admits a bb-coloring with kk colors. El Sahili and Kouider conjectured that b(G)=d+1b(G)=d+1 for a dd-regular graph with girth 5. In this paper, we prove that this conjecture holds for a dd-regular graph, d≥7d≥7, with at least d3+dd3+d vertices. More precisely, we show that b(G)=d+1b(G)=d+1 for a dd-regular graph, d≥7d≥7, with at least d3+dd3+d vertices and containing no cycle of order 4. We also prove that b(G)=d+1b(G)=d+1 for a dd-regular graph, d≥7d≥7, with at least 2d3+2d−2d22d3+2d−2d2 vertices improving Cabello and Jakovac bound.