Game Chromatic Number of a Cartesian Product Graph

Emrah Akyar
Anadolu University

Ummahan Akcan
Anadolu University

Handan Akyar
Anadolu University

PDF

Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

Content: In this study we consider a graph coloring game invented by Bodlaender and Brams independently. Let $G=(V,E)$ be a finite simple graph and $X$ be a set of colors. The game chromatic number of $G$ is defined via a two-person finite game. Two players, generally called Alice and Bob, with Alice going first, alternatively color the uncolored vertices of $G$ with a color from a color set $X$, such that no two adjacent vertices have the same color. Bob wins if at any stage of the game before the $G$ is completely colored, one of the players has no legal move; otherwise, that is, if all the vertices of $G$ are colored properly, Alice wins. The \emph{game chromatic number} $\chi_g(G)$ of $G$ is the least number of colors in the color set $X$ for which Alice has a winning strategy. In this talk we give an exact value for the game chromatic number of the Cartesian product graph $W_n \Box P_2$ of two graphs, $n$-wheel $W_n$ and the path graph $P_2$. This extends a previous work of Sia on the game chromatic number of certain families of Cartesian product graphs. We prove that the game chromatic number of graph $W_n \Box P_2$ is 5, if $n\ge 3$.

Back to all abstracts