b-Chromatic Number of Cartesian Product of Some Families of Graphs

Autor: T. Kavaskar, S. Francis Raj, R. Balakrishnan
Rok vydání: 2013
Předmět:
Zdroj: Graphs and Combinatorics. 30:511-520
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-013-1285-0
Popis: 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 is known that for any two graphs G and H, $${b(G \square H) \geq {\rm {max}} \{b(G), b(H)\}}$$ , where $${\square}$$ stands for the Cartesian product. In this paper, we determine some families of graphs G and H for which strict inequality holds. More precisely, we show that for these graphs G and H, $${b(G \square H) \geq b(G) + b(H) - 1}$$ . This generalizes one of the results due to Kouider and Maheo.
Databáze: OpenAIRE
Externí odkaz: