The b-chromatic number of powers of cycles
Anja Kohl
Abstract
A b-coloring of a graph G by k
colors is a proper vertex coloring such that each color class contains
a color-dominating vertex, that is, a vertex having neighbors in all
other k-1 color classes. The b-chromatic
number χb(G) is the maximum integer
k for which G has a b-coloring
by k colors. Let Cnr
be the rth power of a cycle of order n. In
2003, Effantin and Kheddouci established the b-chromatic
number χb(Cnr) for
all values of n and r, except for
2r+3≤n≤3r. For the missing cases they
presented the lower bound L:= min {n-r-1,r+1+⌊
n-r-1 / 3⌋} and conjectured that
χb(Cnr)=L. In this
paper, we determine the exact value on
χb(Cnr) for the
missing cases. It turns out that
χb(Cnr)>L for
2r+3≤n≤2r+3+r-6 / 4.
Full Text: PDF PostScript