Game chromatic number of Cartesian and corona product graphs
Keywords:
Game chromatic number, Cartesian product, Corona product
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 [5] 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}$.
References
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.
H. L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2(2) (1991) 133–147.
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.
H. A. Kierstead, W. T. Trotter, Planar graph coloring with uncooperative partner, J. Graph Theory 18(6) (1994) 569–584.
C. Sia, The game chromatic number of some families of Cartesian product graphs, AKCE Int. J. Graphs Comb. 6(2) (2009) 315–327.
X. Zhu, Game coloring the Cartesian product of graphs, J. Graph Theory 59(4) (2008) 261–278.
H. L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2(2) (1991) 133–147.
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.
H. A. Kierstead, W. T. Trotter, Planar graph coloring with uncooperative partner, J. Graph Theory 18(6) (1994) 569–584.
C. Sia, The game chromatic number of some families of Cartesian product graphs, AKCE Int. J. Graphs Comb. 6(2) (2009) 315–327.
X. Zhu, Game coloring the Cartesian product of graphs, J. Graph Theory 59(4) (2008) 261–278.
