History

Please fill in your query. A complete syntax description you will find on the General Help page.
On the $b$-chromatic number of regular graphs. (English)
Discrete Appl. Math. 159, No. 13, 1303-1310 (2011).
Summary: The $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 $2d^{3}$ vertices has b-chromatic number $d+1$, the b-chromatic number of an arbitrary $d$-regular graph with girth $g=5$ is at least $\lfloor \frac {d+1}{2}\rfloor$ and every $d$-regular graph, $d\geq 6$, with diameter at least $d$ and with no 4-cycles, has b-chromatic number $d+1$.