Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1002/jgt.21659 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
homomorphism,complexity,sparse graphs | Odd graph,Topology,Discrete mathematics,Indifference graph,Combinatorics,Graph homomorphism,Chordal graph,Clique-sum,Cograph,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
73.0 | 1.0 | 0364-9024 |
Citations | PageRank | References |
8 | 0.83 | 22 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| louis esperet | 1 | 148 | 24.86 |
| Mickaël Montassier | 2 | 288 | 28.20 |
| Pascal Ochem | 3 | 258 | 36.91 |
| Alexandre Pinlou | 4 | 167 | 20.47 |