Game chromatic number of Cartesian and corona product graphs

Syed Ahtsham Ul Haq Bokhary, Tanveer Iqbal, Usman Ali

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}$.

Full Text:

PDF

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.


Refbacks

  • There are currently no refbacks.


ISSN: 2148-838X