×

Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests. (English) Zbl 1455.05059

Summary: In 1976, Steinberg conjectured that planar graphs without 4-cycles and 5-cycles are 3-colorable. This conjecture attracted numerous researchers for about 40 years, until it was recently disproved by V. Cohen-Addad et al. [J. Comb. Theory, Ser. B 122, 452–456 (2017; Zbl 1350.05018)]. However, coloring planar graphs with restrictions on cycle lengths is still an active area of research, and the interest in this particular graph class remains.
Let \(G\) be a planar graph without 4-cycles and 5-cycles. For integers \(d_1\) and \(d_2\) satisfying \(d_1 + d_2 \geq 8\) and \(d_2 \geq d_1 \geq 2\), it is known that \(V(G)\) can be partitioned into two sets \(V_1\) and \(V_2\), where each \(V_i\) induces a graph with maximum degree at most \(d_i\). Since Steinberg’s Conjecture is false, a partition of \(V(G)\) into two sets, where one induces an empty graph and the other induces a forest is not guaranteed. Our main theorem is at the intersection of the two aforementioned research directions. We prove that \(V (G)\) can be partitioned into two sets \(V_1\) and \(V_2\), where \(V_1\) induces a forest with maximum degree at most 3 and \(V_2\) induces a forest with maximum degree at most 4; this is both a relaxation of Steinberg’s conjecture and a strengthening of results by P. Sittitrai and K. Nakprasit [Discrete Math. 341, No. 8, 2142–2150 (2018; Zbl 1388.05072)] in a much stronger form.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abbott, H. L.; Zhou, B., On small faces in 4-critical planar graphs, Ars Combin., 32, 203-207 (1991) · Zbl 0755.05062
[2] Appel, K.; Haken, W., Every planar map is four colorable. I. Discharging, Illinois J. Math., 21, 3, 429-490 (1977) · Zbl 0387.05009
[3] 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
[4] Borodin, O. V., A proof of B. Grünbaum’s conjecture on the acyclic \(5\)-colorability of planar graphs, Dokl. Akad. Nauk SSSR, 231, 1, 18-20 (1976) · Zbl 0363.05031
[5] Borodin, O. V., Structural properties of plane graphs without adjacent triangles and an application to \(3\)-colorings, J. Graph Theory, 21, 2, 183-186 (1996) · Zbl 0838.05039
[6] Borodin, O. V., To the paper: “On small faces in \(4\)-critical planar graphs” [Ars Combin. 32 (1991), 203-207; MR1148923] by H. L. Abbott and B. Zhou, Ars Combin., 43, 191-192 (1996) · Zbl 0881.05037
[7] Borodin, O. V., Colorings of plane graphs: A survey, Discrete Math., 313, 4, 517-539 (2013) · Zbl 1259.05042
[8] Borodin, O. V.; Glebov, A. N., On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph, Diskretn. Anal. Issled. Oper. Ser. 1, 8, 4, 34-53 (2001) · Zbl 1012.05133
[9] 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, 2, 303-311 (2005) · Zbl 1056.05052
[10] 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
[11] Borodin, O. V.; Kostochka, A. V., Defective 2-colorings of sparse graphs, J. Combin. Theory Ser. B, 104, 72-80 (2014) · Zbl 1282.05041
[12] Choi, H.; Choi, I.; Jeong, J.; Suh, G., \( ( 1 , k )\)-coloring of graphs with girth at least five on a surface, J. Graph Theory, 84, 4, 521-535 (2017) · Zbl 1359.05099
[13] Choi, I.; Esperet, L., Improper coloring of graphs on surfaces, J. Graph Theory, 91, 1, 16-34 (2019) · Zbl 1418.05062
[14] Choi, I.; Yu, G.; Zhang, X., Planar graphs with girth at least 5 are \(( 3 , 4 )\)-colorable, Discrete Math., 342, 12, Article 111577 pp. (2019) · Zbl 1422.05035
[15] 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 (2017) · Zbl 1350.05018
[16] 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
[17] Dross, F.; Montassier, M.; Pinlou, A., Partitioning a triangle-free planar graph into a forest and a forest of bounded degree, European J. Combin., 66, 81-94 (2017) · Zbl 1369.05169
[18] Grötzsch, H., 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, 109-120 (1958)
[19] Liu, L.; Lv, J., Every planar graph without \(4\)-cycles and \(5\)-cycles is \(( 2 , 6 )\)-colorable, Bull. Malays. Math. Sci. Soc., 43, 2493-2507 (2020) · Zbl 1437.05077
[20] Montassier, M.; Ochem, P., Near-colorings: non-colorable graphs and NP-completeness, Electron. J. Combin., 22, 1, P1.57 (2015) · Zbl 1308.05052
[21] Poh, K. S., On the linear vertex-arboricity of a planar graph, J. Graph Theory, 14, 1, 73-75 (1990) · Zbl 0705.05016
[22] Sanders, D. P.; Zhao, Y., A note on the three color problem, Graphs Combin., 11, 1, 91-94 (1995) · Zbl 0824.05023
[23] Sittitrai, P.; Nakprasit, K., Defective 2-colorings of planar graphs without 4-cycles and 5-cycles, Discrete Math., 341, 8, 2142-2150 (2018) · Zbl 1388.05072
[24] Steinberg, R., The state of the three color problem, (Quo Vadis, Graph Theory?. Quo Vadis, Graph Theory?, Ann. Discrete Math., vol. 55 (1993), North-Holland, Amsterdam), 211-248 · Zbl 0791.05044
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.