On the b-chromatic number of some graph products
Marko Jakovac, Iztok Peterin · Studia Scientiarum Mathematicarum Hungarica · 2012
A b-coloring is a proper vertex coloring of a graph such that each color class contains a vertex that has a neighbor in all other color classes and the b-chromatic number is the largest integer φ(G) for which a graph has a b-coloring with φ(G) colors. We determine some upper and lower bounds for the b-chromatic number of the strong product G ⊠ H, the lexicographic product G[H] and the direct product G × H and give some exact values for products of paths, cycles, stars, and complete bipartite graphs. We also show that the b-chromatic number of Pn ⊠ H, Cn ⊠ H, Pn[H], Cn[H], and Km,n[H] can be determined for an arbitrary graph H, when integers m and n are large enough.