×

zbMATH — the first resource for mathematics

Characterization of cycle obstruction sets for improper coloring planar graphs. (English) Zbl 1388.05061

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math., 21 (1977), pp. 429–490. · Zbl 0387.05009
[2] K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math., 21 (1977), pp. 491–567. · Zbl 0387.05010
[3] O. V. Borodin, A. O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud, Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\), J. Graph Theory, 65 (2010), pp. 83–93. · Zbl 1209.05177
[4] O. V. Borodin, A. Kostochka, and M. Yancey, On 1-improper 2-coloring of sparse graphs, Discrete Math., 313 (2013), pp. 2638–2649. · Zbl 1281.05060
[5] O. V. Borodin and A. V. Kostochka, Defective 2-colorings of sparse graphs, J. Combin. Theory Ser. B, 104 (2014), pp. 72–80. · Zbl 1282.05041
[6] M. Chen, A. Raspaud, and W. Wang, Three-coloring planar graphs without short cycles, Inform. Process. Lett., 101 (2007), pp. 134–138. · Zbl 1185.05057
[7] H. Choi, I. Choi, J. Jeong, and G. Suh, \((1, k)\)-coloring of graphs with girth at least five on a surface, J. Graph Theory, 84 (2017), pp. 521–535. · Zbl 1359.05099
[8] I. Choi and L. Esperet, Improper Coloring of Graphs on Surfaces, preprint, arXiv:1603.02841, 2016.
[9] I. Choi and A. Raspaud, Planar graphs with girth at least 5 are (3, 5)-colorable, Discrete Math., 338 (2015), pp. 661–667. · Zbl 1305.05072
[10] V. Cohen-Addad, M. Hebdige, D. Král’, Z. Li, and E. Salgado, Steinberg’s conjecture is false, J. Combin. Theory Ser. B, 122 (2017), pp. 452–456. · Zbl 1350.05018
[11] L. J. Cowen, R. H. Cowen, and D. R. Woodall, Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency, J. Graph Theory, 10 (1986), pp. 187–195. · Zbl 0596.05024
[12] L. Esperet, M. Montassier, P. Ochem, and A. Pinlou, A complexity dichotomy for the coloring of sparse graphs, J. Graph Theory, 73 (2013), pp. 85–102. · Zbl 1264.05049
[13] H. Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe, 8 (1958/1959), pp. 109–120.
[14] F. Havet and J.-S. Sereni, Improper choosability of graphs and maximum average degree, J. Graph Theory, 52 (2006), pp. 181–199. · Zbl 1104.05026
[15] J. Kim, A. Kostochka, and X. Zhu, Improper coloring of sparse graphs with a given girth, I: \((0,1)\)-colorings of triangle-free graphs, European J. Combin., 42 (2014), pp. 26–48. · Zbl 1297.05083
[16] J. Kim, A. Kostochka, and X. Zhu, Improper coloring of sparse graphs with a given girth, II: Constructions, J. Graph Theory, 81 (2016), pp. 403–413. · Zbl 1333.05115
[17] M. Montassier and P. Ochem, Near-colorings: Non-colorable graphs and NP-completeness, Electron. J. Combin., 22 (2015), Paper 1.57, 13. · Zbl 1308.05052
[18] N. Robertson, D. Sanders, P. Seymour, and R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B, 70 (1997), pp. 2–44. · Zbl 0883.05056
[19] R. Škrekovski, List improper colorings of planar graphs with prescribed girth, Discrete Math., 214 (2000), pp. 221–233.
[20] R. Steinberg, The state of the three color problem, in Quo Vadis, Graph Theory?, Ann. Discrete Math. 55, North-Holland, Amsterdam, 1993, pp. 211–248.
[21] W.-F. Wang and M. Chen, Planar graphs without 4,6,8-cycles are 3-colorable, Sci. China Ser. A Math., 50 (2007), pp. 1552–1562. · Zbl 1144.05033
[22] Y. Wang, H. Lu, and M. Chen, Planar graphs without cycles of length 4, 5, 8 or 9 are 3-choosable, Discrete Math., 310 (2010), pp. 147–158. · Zbl 1228.05131
[23] Y. Wang, Q. Wu, and L. Shen, Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable, Discrete Appl. Math., 159 (2011), pp. 232–239. · Zbl 1210.05029
[24] B. Xu, On \(3\)-colorable plane graphs without 5- and 7-cycles, J. Combin. Theory Ser. B, 96 (2006), pp. 958–963. · Zbl 1108.05046
[25] L. Zhang and B. Wu, A note on 3-choosability of planar graphs without certain cycles, Discrete Math., 297 (2005), pp. 206–209. · Zbl 1070.05046
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.