On two conjectures on b-coloring of graph products
S. Francis Raj, T. Kavaskar · Studia Scientiarum Mathematicarum Hungarica · 2017
A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. It was conjectured in [10], that for any two graphs G and H, b(G[H]) ≦ b(G) − 1|V (H)| + Δ(H) + 1 and b(G ⊠ H) ≦ max {b(G)(Δ(H) + 1), b(H) Δ(G) + 1)}, where G[H] and G ⊠ H denotes the lexicographic product and the strong product of G and H, respectively. In this paper, we disprove both conjectures.