2013/02/18 by Amine El Sahili, Sahili, Amine El, Mekkia Kouider +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1302.4209
arxiv created 2013/02/18 · arxiv updated 2013/02/19
A b-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 b-chromatic number of a graph G, denoted by b(G), is the maximum integer k such that G admits a b-coloring with k colors. El Sahili and Kouider conjectured that b(G)=d+1 for d-regular graph with girth 5, d≥4. In this paper, we prove that this conjecture holds for d-regular graph with at least d3+d vertices. More precisely we show that b(G)=d+1 for d-regular graph with at least d3+d vertices and containing no cycle of order 4. We also prove that b(G)=d+1 for d-regular graphs with at least 2d3+2d-2d2 vertices improving Cabello and Jakovac bound.