×

zbMATH — the first resource for mathematics

Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8. (English) Zbl 1379.05034
Summary: We introduce a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of O. V. Borodin [Discrete Math. 313, No. 4, 517–539 (2013; Zbl 1259.05042)].

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., Degrees and choice numbers, Random Structures Algorithms, 16, 364-368, (2000) · Zbl 0958.05049
[2] Appel, K.; Haken, W., Every planar map is four colorable. part I: discharging, Illinois J. Math., 21, 429-490, (1977) · Zbl 0387.05009
[3] Bernshteyn, A., The asymptotic behavior of the correspondence chromatic number, Discrete Math., 339, 2680-2692, (2016) · Zbl 1339.05111
[4] Bernshteyn, A.; Kostochka, A., Sharp Dirac’s theorem for DP-critical graphs, (2016) · Zbl 1393.05106
[5] Bernshteyn, A.; Kostochka, A.; Pron, S., On DP-coloring of graphs and multigraphs, Sib. Mat. J., 58, 28-36, (2017) · Zbl 1366.05038
[6] M. Bonamy, T. Perrett, L. Postle, Colouring graphs with sparse neighbourhoods: Bounds and applications, manuscript, 2016.
[7] Borodin, O. V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. Graph Theory, 21, 183-186, (1996) · Zbl 0838.05039
[8] Borodin, O., Colorings of plane graphs: a survey, Discrete Math., 313, 517-539, (2013) · Zbl 1259.05042
[9] Borodin, O. V.; Glebov, A. N.; Montassier, M.; Raspaud, A., Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable, J. Combin. Theory Ser. B, 99, 668-673, (2009) · Zbl 1184.05024
[10] Borodin, O. V.; Glebov, A. N.; Raspaud, A.; Salavatipour, M. R., Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B, 93, 303-311, (2005) · Zbl 1056.05052
[11] Cohen-Addad, V.; Hebdige, M.; Král’, D.; Li, Z.; Salgado, E., Steinberg’s conjecture is false, J. Combin. Theory Ser. B, 122, 452-456, (2016) · Zbl 1350.05018
[12] Grötzsch, H., Ein dreifarbensatz für dreikreisfreie netze auf der kugel, Math.-Natur. Reihe, 8, 109-120, (1959)
[13] Steinberg, R., The state of the three color problem. quo vadis, graph theory?, Ann. Discrete Math., 55, 211-248, (1993)
[14] Thomassen, C., Every planar graph is 5-choosable, J. Combin. Theory Ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[15] Thomassen, C., 3-List-coloring planar graphs of girth 5, J. Combin. Theory Ser. B, 64, 101-107, (1995) · Zbl 0822.05029
[16] Voigt, M., List colourings of planar graphs, Discrete Math., 120, 215-219, (1993) · Zbl 0790.05030
[17] Voigt, M., A not 3-choosable planar graph without 3-cycles, Discrete Math., 146, 325-328, (1995) · Zbl 0843.05034
[18] Voigt, M., A non-3-choosable planar graph without cycles of length 4 and 5, Discrete Math., 307, 1013-1015, (2007) · Zbl 1112.05041
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.