Game chromatic number of Cartesian and corona product graphs

Year 2018, , 129 - 136, 08.10.2018

Syed Ahtsham Ul Haq Bokhary , Tanveer Iqbal Usman Ali

https://doi.org/10.13069/jacodesmath.458240

Cited By: 1

Abstract

The game chromatic number $\chi_g$ is investigated for Cartesian
product $G\square H$ and corona product $G\circ H$ of two graphs $G$
and $H$. The exact values for the game chromatic number of Cartesian
product graph of $S_{3}\square S_{n}$ is found, where $S_n$ is a
star graph of order $n+1$. This extends previous results of
Bartnicki et al. [1] and Sia [9] on the game chromatic
number of Cartesian product graphs. Let $P_m$ be the path graph on
$m$ vertices and $C_n$ be the cycle graph on $n$ vertices. We have
determined the exact values for the game chromatic number of corona
product graphs $P_{m}\circ K_{1}$ and $P_{m}\circ C_{n}$.

Keywords

Game chromatic number, Cartesian product, Corona product

References

• [1] T. Bartnicki, B. Brešar, J. Grytczuk, M. Kovše, Z. Miechowicz, I. Peterin, Game chromatic number of Cartesian product graphs, Electron. J. Combin. 15 (2008) R72.
• [2] H. L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2(2) (1991) 133–147.
• [3] U. Faigle, U. Kern, H. Kierstead, W. T. Trotter, On the game chromatic number of some classes of graphs, Ars Combin. 35 (1993) 143–150.
• [4] H. A. Kierstead, W. T. Trotter, Planar graph coloring with uncooperative partner, J. Graph Theory 18(6) (1994) 569–584.
• [5] C. Sia, The game chromatic number of some families of Cartesian product graphs, AKCE Int. J. Graphs Comb. 6(2) (2009) 315–327.
• [6] X. Zhu, Game coloring the Cartesian product of graphs, J. Graph Theory 59(4) (2008) 261–278.