On the b-chromatic number of rooted product graphs

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 sufficient 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.