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 P n denote the path with n ≥ 1 vertices. For instance, in the case of Cartesian grids, it is easy to show that χ g ( P m □ P n ) ≤ 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 (P 1 □ P n ) = 3, χ g (P 2 □ P n ) = 4 and χ g ( P 3 □ Pn ) = 4 for n ≥ 4 [Raspaud, Wu, 2009]. Here, we prove that, for every n ≥ 18, χ g ( P 4 □ P n ) = 4.

Motivated by the problem of enumerating all tree decompositions of a graph, we consider in this article the problem of listing all the minimal chordal completions of a graph. In [Carmeli et al., 2020] (Pods 2017) Carmeli et al. proved that all minimal chordal completions or equivalently all proper tree decompositions of a graph can be listed in incremental polynomial time using exponential space. The total running time of their algorithm is quadratic in the number of solutions and the existence of an algorithm whose complexity depends only linearly on the number of solutions remained open. We close this question by providing a polynomial delay algorithm to solve this problem which, moreover, uses polynomial space. Our algorithm relies on Proximity Search, a framework recently introduced by Conte and Uno [Conte and Uno, 2019] (Stoc 2019) which has been shown powerful to obtain polynomial delay algorithms, but generally requires exponential space. In order to obtain a polynomial space algorithm for our problem, we introduce a new general method called canonical path reconstruction to design polynomial delay and polynomial space algorithms based on proximity search.