Game chromatic number of Cartesian and corona product graphs

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. [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. [2] H. L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2(2) (1991) 133–147.
3. [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. [4] H. A. Kierstead, W. T. Trotter, Planar graph coloring with uncooperative partner, J. Graph Theory 18(6) (1994) 569–584.
5. [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. [6] X. Zhu, Game coloring the Cartesian product of graphs, J. Graph Theory 59(4) (2008) 261–278.