×

Planar graphs with girth at least 5 are \((3, 4)\)-colorable. (English) Zbl 1422.05035

Summary: A graph is \((d_1, \ldots, d_k)\)-colorable if its vertex set can be partitioned into \(k\) nonempty subsets so that the subgraph induced by the \(i\)-th part has maximum degree at most \(d_i\) for each \(i \in \{1, \ldots, k \}\). It is known that for each pair \((d_1, d_2)\), there exists a planar graph with girth \(4\) that is not \((d_1, d_2)\)-colorable. This sparked the interest in finding the pairs \((d_1, d_2)\) such that planar graphs with girth at least \(5\) are \((d_1, d_2)\)-colorable. Given \(d_1 \leq d_2\), it is known that planar graphs with girth at least \(5\) are \((d_1, d_2)\)-colorable if either \(d_1 \geq 2\) and \(d_1 + d_2 \geq 8\) or \(d_1 = 1\) and \(d_2 \geq 10\). We improve an aforementioned result by providing the first pair \((d_1, d_2)\) in the literature satisfying \(d_1 + d_2 \leq 7\) where planar graphs with girth at least \(5\) are \((d_1, d_2)\)-colorable. Namely, we prove that planar graphs with girth at least \(5\) are \((3, 4)\)-colorable.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Appel, K.; Haken, W., Every planar map is four colorable. I. Discharging, Illinois J. Math., 21, 3, 429-490 (1977) · Zbl 0387.05009
[2] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable. II. Reducibility, Illinois J. Math., 21, 3, 491-567 (1977) · Zbl 0387.05010
[3] Borodin, O. V.; Ivanova, A. O.; Montassier, M.; Ochem, P.; Raspaud, A., Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\), J. Graph Theory, 65, 2, 83-93 (2010) · Zbl 1209.05177
[4] Borodin, O. V.; Kostochka, A. V., Vertex decompositions of sparse graphs into an independent set and a subgraph of maximum degree at most 1, Sib. Mat. Z., 52, 5, 1004-1010 (2011) · Zbl 1232.05073
[5] Borodin, O. V.; Kostochka, A. V., Defective 2-colorings of sparse graphs, J. Combin. Theory Ser. B, 104, 72-80 (2014) · Zbl 1282.05041
[6] Borodin, O. V.; Kostochka, A.; Yancey, M., On 1-improper 2-coloring of sparse graphs, Discrete Math., 313, 22, 2638-2649 (2013) · Zbl 1281.05060
[7] Choi, Hojin; Choi, Ilkyoo; Jeong, Jisu; Suh, Geewon, \((1, k)\)-coloring of graphs with girth at least five on a surface, J. Graph Theory, 84, 4, 521-535 (2017) · Zbl 1359.05099
[8] I. Choi, L. Esperet, Improper coloring of graphs on surfaces, 2016, ArXiv e-prints arXiv:1603.02841; I. Choi, L. Esperet, Improper coloring of graphs on surfaces, 2016, ArXiv e-prints arXiv:1603.02841
[9] Choi, Ilkyoo; Raspaud, André, Planar graphs with girth at least \(5\) are \((3, 5)\)-colorable, Discrete Math., 338, 4, 661-667 (2015) · Zbl 1305.05072
[10] Cowen, L. J.; Cowen, R. H.; Woodall, D. R., Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory, 10, 2, 187-195 (1986) · Zbl 0596.05024
[11] Eaton, Nancy; Hull, Thomas, Defective list colorings of planar graphs, Bull. Inst. Combin. Appl., 25, 79-87 (1999) · Zbl 0916.05026
[12] Grötzsch, Herbert, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenb. Math.-Nat. Reihe, 8, 109-120 (1958)
[13] Havet, Frédéric; Sereni, Jean-Sébastien, Improper choosability of graphs and maximum average degree, J. Graph Theory, 52, 3, 181-199 (2006) · Zbl 1104.05026
[14] Montassier, M.; Ochem, P., Near-colorings: non-colorable graphs and NP-completeness, Electron. J. Combin., 22, 1,1.57, 13 (2015) · Zbl 1308.05052
[15] Škrekovski, R., List improper colourings of planar graphs, Combin. Probab. Comput., 8, 3, 293-299 (1999) · Zbl 0940.05031
[16] Škrekovski, Riste, List improper colorings of planar graphs with prescribed girth, Discrete Math., 214, 1-3, 221-233 (2000) · Zbl 0940.05027
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.