Event calendar file
19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
On the b-chromatic number of regular graphs
Presented by Mr. Marko JAKOVAC
Type: Oral presentation
Track: Coloring of Graphs
Content
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$, that the b-chromatic number of an arbitrary $d$-regular graph with girth $g=5$ is at least $\left\lfloor\frac{d+1}{2}\right\rfloor$ and that every $d$-regular graph, $d \geq 6$, with diameter at least $d$ and with no $4$-cycles admits a b-coloring with $d+1$ colors.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
