Game chromatic number of Cartesian and corona product graphs
DOI:
https://doi.org/10.13069/jacodesmath.458240Keywords:
Game chromatic number, Cartesian product, Corona productAbstract
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}$.
Received: 17 February 2017 Accepted: 10 April 2018
Downloads
References
T. Bartnicki, B. Brešar, J. Grytczuk, M. Kovše, Z. Miechowicz, and 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. A. Kierstead, and W. T. Trotter, On the game chromatic number of some classes of graphs, Ars Combin. 35 (1993) 143–150.
H. A. Kierstead and W. T. Trotter, Planar graph coloring with an 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.
