A Complexity Dichotomy for the Coloring of Sparse Graphs

Galluccio, Goddyn, and Hell proved in 2001 that in any minor-closed class of graphs, graphs with large enough girth have a homomorphism to any given odd cycle. In this paper, we study the computational aspects of this problem. Let F be a monotone class of graphs containing all planar graphs, and closed under clique-sum of order at most two. Examples of such class include minor-closed classes containing all planar graphs, and such that all minimal obstructions are 3-connected. We prove that for any k and g, either every graph of girth at least g in F has a homomorphism to C2k+1, or deciding whether a graph of girth g in F has a homomorphism to C2k+1 is NP-complete. We also show that the same dichotomy occurs when considering 3-Colorability or acyclic 3-Colorability of graphs under various notions of density that are related to a question of Havel (On a conjecture of Grunbaum, J Combin Theory Ser B 7 (1969), 184186) and a conjecture of Steinberg (The state of the three color problem, Quo Vadis, Graph theory?, Ann Discrete Math 55 (1993), 211248) about the 3-Colorability of sparse planar graphs.