Syed Ahtsham Ul Haq BOKHARY, Tanveer IQBAL, Usman ALİ

Game chromatic number of Cartesian and corona product graphs

Başlangıç: 2015
Yayıncı: İrfan ŞİAP

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,

PDF

___

[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.