# zbMATH — the first resource for mathematics

A complexity dichotomy for the coloring of sparse graphs. (English) Zbl 1264.05049
Summary: A. Galluccio et al. [J. Comb. Theory, Ser. B 83, No.1, 1–14 (2001; Zbl 1028.05034)] proved 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 $$\mathcal 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 $$\mathcal F$$ has a homomorphism to $$C_{2k+1}$$, or deciding whether a graph of girth $$g$$ in $$\mathcal F$$ has a homomorphism to $$C_{2k+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 I. Havel [J. Comb. Theory 7, 184–186 (1969; Zbl 0177.26805)] and a conjecture of R. Steinberg [Ann. Discrete Math. 55, 211–248 (1993; Zbl 0791.05044)] about the 3-Colorability of sparse planar graphs.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C83 Graph minors
##### Keywords:
homomorphism; complexity; sparse graphs
Full Text:
##### References:
 [1] Abbott, On small faces in 4-critical graphs, Ars Combin 32 pp 203– (1991) · Zbl 0755.05062 [2] Aksionov, Some counterexamples associated with the three color problem, J Combin Theory Ser B 28 (1) pp 1– (1980) · Zbl 0434.05033 · doi:10.1016/0095-8956(80)90051-9 [3] Borodin, To the paper of H.L. Abbott and B. Zhou on 4-critical planar graphs, Ars Combin 43 pp 191– (1996) [4] Borodin, Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J Graph Theory 21 (2) pp 183– (1996) · Zbl 0838.05039 · doi:10.1002/(SICI)1097-0118(199602)21:2<183::AID-JGT7>3.0.CO;2-N [5] Borodin, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J Combin Theory Ser B 93 pp 303– (2005) · Zbl 1056.05052 · doi:10.1016/j.jctb.2004.11.001 [6] Borodin, Near-proper list vertex 2-colorings of sparse graphs, Diskretn Anal Issled Oper 16 (2) pp 16– (2009) · Zbl 1249.05110 [7] Borodin, Acyclic 3-choosability of planar graphs with no cycles of length 4 to 11, Sib Élektron Mat Izv 7 pp 16– (2010) · Zbl 1329.05101 [8] Borodin, Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k, J Graph Theory 65 (2) pp 83– (2010) · Zbl 1209.05177 · doi:10.1002/jgt.20467 [9] Borodin, Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1, Siberian Math J 52 (5) pp 796– (2011) · Zbl 1232.05073 [10] Borodin, Homomorphisms from sparse graphs with large girth, J Combin Theory Ser B 90 pp 147– (2004) · Zbl 1033.05037 · doi:10.1016/S0095-8956(03)00081-9 [11] Borodin, Acyclic colourings of planar graphs with large girth, J Lond Math Soc 60 pp 344– (1999) · Zbl 0940.05032 · doi:10.1112/S0024610799007942 [12] de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, J Combin Theory Ser B 50 pp 11– (1990) · Zbl 0742.05061 · doi:10.1016/0095-8956(90)90093-F [13] Z. Dvořák D. Král’ R. Thomas Coloring planar graphs with triangles far apart 2009 http://arxiv.org/abs/0911.0885 [14] Edmonds, A minor-monotone graph parameter on oriented matroids, Discrete Math 165/166 pp 219– (1997) · Zbl 0873.05030 · doi:10.1016/S0012-365X(96)00172-0 [15] Galluccio, High-girth graphs avoiding a minor are nearly bipartite, J Combin Theory Ser B 83 (1) pp 1– (2001) · Zbl 1028.05034 · doi:10.1006/jctb.2000.2009 [16] Garey, Some simplified NP-complete graph problems, Theor Comput Sci 1 pp 237– (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1 [17] H. Gebauer T. Szabó G. Tardos The local lemma is tight for SAT Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms 2011 San Francisco, CA, USA 664 674 · Zbl 1373.68270 [18] Glebov, Path partitions of planar graph, Sib Élektron Mat Izv 4 pp 450– (2007) · Zbl 1132.05315 [19] Grötzsch, Ein Dreifarbenzatz für dreikreisfreie Netze auf der Kugel, Math-Nat Reihe 8 pp 109– (1959) [20] Havel, On a conjecture of Grünbaum, J Combin Theory Ser B 7 pp 184– (1969) · Zbl 0177.26805 · doi:10.1016/S0021-9800(69)80054-2 [21] van der Holst, On a minor-monotone graph invariant, J Combin Theory Ser B 65 (2) pp 291– (1995) · Zbl 0839.05034 · doi:10.1006/jctb.1995.1056 [22] van der Holst, On the behaviour of Colin de Verdière’s invariant under clique sums, Linear Algebra Appl 226-228 pp 508– (1995) · Zbl 0834.05036 · doi:10.1016/0024-3795(95)00160-S [23] Jaeger, Selected Topics in Graph Theory 3 pp 91– (1988) [24] Klostermeyer, (2+$$\epsilon$$)-Coloring of planar graphs with large odd girth, J Graph Theory 33 pp 109– (2000) · Zbl 0944.05046 · doi:10.1002/(SICI)1097-0118(200002)33:2<109::AID-JGT5>3.0.CO;2-F [25] Kratochvíl, One more occurrence of variables makes satisfiability jump from trivial to NP-complete, SIAM J Comput 22 pp 203– (1993) · Zbl 0767.68057 · doi:10.1137/0222015 [26] Lichtenstein, Planar formulae and their uses, SIAM J Comput 11 (2) pp 329– (1982) · Zbl 0478.68043 · doi:10.1137/0211025 [27] Lovász, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc Am Math Soc 126 pp 1275– (1998) · Zbl 0886.05055 · doi:10.1090/S0002-9939-98-04244-0 [28] MacGillivray, On the complexity of H-colouring planar graphs, Discrete Math 309 (18) pp 5729– (2009) · Zbl 1213.05094 · doi:10.1016/j.disc.2008.05.016 [29] P. Ochem Graph coloring and combinatorics on words 2005 [30] Robertson, Sachs’ linkless embedding conjecture, J Combin Theory Ser B 64 (2) pp 185– (1995) · Zbl 0832.05032 · doi:10.1006/jctb.1995.1032 [31] M. R. Salavatipour The three color problem for planar graphs 2002 [32] Sanders, A note on the three color problem, Graphs Combin 11 pp 91– (1995) · Zbl 0824.05023 · doi:10.1007/BF01787424 [33] Steinberg, The state of the three color problem, Quo Vadis, Graph theory? Ann Discrete Math 55 pp 211– (1993) · doi:10.1016/S0167-5060(08)70391-1 [34] Tovey, A simplified NP-complete satisfiability problem, Discrete Appl Math 8 pp 85– (1984) · Zbl 0534.68028 · doi:10.1016/0166-218X(84)90081-7 [35] Tutte, A contribution on the theory of chromatic polynomial, Can J Math 6 pp 80– (1954) · Zbl 0055.17101 · doi:10.4153/CJM-1954-010-9 [36] Tutte, On the algebraic theory of graph colorings, J Combin Theory 1 pp 15– (1966) · Zbl 0139.41402 · doi:10.1016/S0021-9800(66)80004-2 [37] Xu, Note on acyclic colorings of graphs, Ars Combin 72 pp 235– (2004) · Zbl 1077.05047 [38] Youngs, 4-Chromatic projective graphs, J Graph Theory 21 pp 219– (1996) · Zbl 0839.05040 · doi:10.1002/(SICI)1097-0118(199602)21:2<219::AID-JGT12>3.0.CO;2-E [39] Zhu, Circular chromatic number of planar graphs of large odd girth, Electron J Combin 8 pp #R25– (2001) · Zbl 0969.05022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.