On the b-chromatic number of regular graphs

AbstractThe b-chromatic number of a graph G is the largest integer k, such that G admits a proper k-coloring in which every color class contains at least one vertex that has a neighbor in each of the other color classes. We prove that every d-regular graph with at least 2d3 vertices has b-chromatic number d+1, the b-chromatic number of an arbitrary d-regular graph with girth g=5 is at least ⌊d+12⌋ and every d-regular graph, d≥6, with diameter at least d and with no 4-cycles, has b-chromatic number d+1