# Bled'11 - 7th Slovenian International Conference on Graph Theory

19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

# 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

More

More