The Graph Coloring Game on $4\times n$-Grids

Abstract

The graph coloring game is a famous two-player game (re)introduced by Bodlaender in $1991$. Given a graph $G$ and $k\in \mathbb{N}$, Alice and Bob alternately (starting with Alice) color an uncolored vertex with some color in $\{1,\cdots ,k\}$ such that no two adjacent vertices receive a same color. If eventually all vertices are colored, then Alice wins and Bob wins otherwise. The game chromatic number $\ddot{I}{‡}_g(G)$ is the smallest integer $k$ such that Alice has a winning strategy with $k$ colors in $G$. It has been recently (2020) shown that, given a graph $G$ and $k\in \mathbb{N}$, deciding whether $\ddot{I}{‡}_g(G)\le k$ is PSPACE-complete. Surprisingly, this parameter is not well understood even in ``simple" graph classes. Let $P_n$ denote the path with $n\ge 1$ vertices. For instance, in the case of Cartesian grids, it is easy to show that $\ddot{I}{‡}_g(P_m\times P_n)\le 5$ since $\ddot{I}{‡}_g(G)\le \hat{I}”+1$ for any graph $G$ with maximum degree $\hat{I}”$. However, the exact value is only known for small values of $m$, namely $\ddot{I}{‡}_g(P_1\times P_n)=3$, $\ddot{I}{‡}_g(P_2\times P_n)=4$ and $\ddot{I}{‡}_g(P_3\times P_n)=4$ for $n\ge 4$ [Raspaud, Wu, 2009]. Here, we prove that, for every $n\ge 18$, $\ddot{I}{‡}_g(P_4\times P_n)=4$.

22 pages, 22 figures