The Graph Coloring Game on 4 × n-Grids

The graph coloring game is a famous two-player game (re)introduced by Bodlaender in 1991. Given a graph G and k ∈ N, Alice and Bob alternately (starting with Alice) color an uncolored vertex with some color in {1, • • • , 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 χ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 ∈ N, deciding whether χg(G) ≤ k is PSPACE-complete. Surprisingly, this parameter is not well understood even in "simple" graph classes. Let Pn denote the path with n ≥ 1 vertices. For instance, in the case of Cartesian grids, it is easy to show that χg(Pm□Pn) ≤ 5 since χg(G) ≤ ∆ + 1 for any graph G with maximum degree ∆. However, the exact value is only known for small values of m, namely χg(P1□Pn) = 3, χg(P2□Pn) = 4 and χg(P3□Pn) = 4 for n ≥ 4 [Raspaud, Wu, 2009]. Here, we prove that, for every n ≥ 18, χg(P4□Pn) = 4.