2024/12/23 by Caroline Brosse, Brosse, Caroline, Nícolas Martins +5
Computer Science · #Advanced Graph Theory Research #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2412.17668
The graph coloring game is a famous two-player game (re)introduced by Bodlaender in 1991. Given a graph G and k ∈ ℕ, 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∈ ℕ, 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.