On the b-chromatic number of rooted product graphs

Abstract

The b-chromatic number of a graph G was defined by Irving and Manlove in
1999 as the largest integer k for which G admits a proper coloring with k colors
such that every color class (in this proper coloring) has a vertex that is adjacent
to at least one vertex in every other color class. The b-chromatic number has
been studied in many contexts, including for various graph products. The rooted
product, defined by Godsil and McKay in 1978, is not yet among these. We find
bounds for the b-chromatic number of the rooted product of two graphs in terms
of the b-chromatic numbers and degrees of the factors, along with some new
parameters that we define. Moreover, we give suficient conditions for equality
to hold in these bounds. We refine our results, sometimes to exact values, when
one or both of the factors is a path, cycle, complete graph, star, or wheel.