A Complexity Dichotomy for the Coloring of Sparse Graphs

Louis Esperet 1 Mickaël Montassier 2 Pascal Ochem 2 Alexandre Pinlou 2
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Gallucio, Goddyn and Hell proved in 2001 that in any minor-closed class, graphs with large enough girth have a homomorphism to any given odd cycle. In this paper, we study the computational aspects of this problem. We show that for any minor-closed class $F$ containing all planar graphs, and such that all minimal forbidden minors are 3-connected, the following holds: for any $k$ there is a $g = g(F, k)$ such that every graph of girth at least $g$ in $F$ has a homomorphism to $C_2k+1$, but deciding whether a graph of girth $g-1$ in $F$ has a homomorphism to $C_2k+1$ is NP-complete. The classes of graphs on which this result applies include planar graphs, $K_n$-minor free graphs, and graphs with bounded Colin de Verdière parameter (for instance, linklessly embeddable graphs). We also show that the same dichotomy occurs in problems related to a question of Havel (1969) and a conjecture of Steinberg (1976) about the 3-colorability of sparse planar graphs.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2013, 73 (1), pp.85-102. 〈http://dx.doi.org/10.1002/jgt.21659〉. 〈10.1002/jgt.21659〉
Liste complète des métadonnées

Contributeur : Alexandre Pinlou <>
Soumis le : vendredi 28 septembre 2012 - 12:07:45
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral



Louis Esperet, Mickaël Montassier, Pascal Ochem, Alexandre Pinlou. A Complexity Dichotomy for the Coloring of Sparse Graphs. Journal of Graph Theory, Wiley, 2013, 73 (1), pp.85-102. 〈http://dx.doi.org/10.1002/jgt.21659〉. 〈10.1002/jgt.21659〉. 〈lirmm-00736468〉



Consultations de la notice