Premium
A Complexity Dichotomy for the Coloring of Sparse Graphs
Author(s) -
Esperet Louis,
Montassier Mickaël,
Ochem Pascal,
Pinlou Alexandre
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21659
Subject(s) - combinatorics , mathematics , discrete mathematics , homomorphism , pathwidth , chordal graph , conjecture , graph homomorphism , planar graph , indifference graph , treewidth , monotone polygon , clique , 1 planar graph , graph , line graph , graph power , geometry
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 C 2 k + 1 , or deciding whether a graph of girth g in F has a homomorphism to C 2 k + 1is 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 Grünbaum, J Combin Theory Ser B 7 (1969), 184–186) and a conjecture of Steinberg (The state of the three color problem, Quo Vadis, Graph theory?, Ann Discrete Math 55 (1993), 211–248) about the 3‐Colorability of sparse planar graphs.