×

zbMATH — the first resource for mathematics

Colouring planar graphs with bounded monochromatic components. (English) Zbl 1440.05086
Summary: O. V. Borodin and A. O. Ivanova [J. Graph Theory 67, No. 2, 83–90 (2011; Zbl 1218.05038)] proved that every planar graph of girth at least 7 is 2-choosable with the property that each monochromatic component is a path with at most 3 vertices. M. Axenovich et al. [J. Graph Theory 85, No. 3, 601–618 (2017; Zbl 1367.05044)] proved that every planar graph of girth 6 is 2-choosable so that each monochromatic component is a path with at most 15 vertices. We improve both these results by showing that planar graphs of girth at least 6 are 2-choosable so that each monochromatic component is a path with at most 3 vertices. Our second result states that every planar graph of girth 5 is 2-choosable so that each monochromatic component is a tree with at most 515 vertices. Finally, we prove that every graph with fractional arboricity at most \(\frac{2d+2}{d+2}\) is 2-choosabale with the property that each monochromatic component is a tree with maximum degree at most \(d\). This implies that planar graphs of girth 5, 6, and 8 are 2-choosable so that each monochromatic component is a tree with maximum degree at most 4, 2, and 1, respectively. All our results are obtained by applying the nine dragon tree theorem, which was recently proved by H. Jiang and D. Yang [Combinatorica 37, No. 6, 1125–1137 (2017; Zbl 1399.05034)], and the strong nine dragon tree conjecture partially confirmed by S.-J. Kim et al. [J. Graph Theory 74, No. 3–4, 369–391 (2013; Zbl 1276.05092)] and B. Moore [“An approximate version of the strong nine dragon tree conjecture”, Preprint, arXiv:1909.07946].
MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Alon, G. Ding, B. Oporowski, D. Vertigan,Partitioning into graphs with only small components, J. Comb. Theory, Ser. B,87:2 (2003), 231-243. Zbl 1023.05045 · Zbl 1023.05045
[2] K. Appel, W. Haken,Every planar map is four colorable. Part I: Discharging, Ill. J. Math., 21:3 (1977), 429-490. Zbl 0387.05009 · Zbl 0387.05009
[3] K. Appel, W. Haken,Every planar map is four colorable. Part II: Reducibility, Ill. J. Math., 21:3 (1977), 491-567. Zbl 0387.05010 · Zbl 0387.05010
[4] M. Axenovich, T. Ueckerdt, P. Weiner,Splitting planar graphs of girth 6 into two linear forests with short paths, J. Graph Theory,85:3 (2017), 601-618. Zbl 1367.05044 · Zbl 1367.05044
[5] O.V. Borodin, A.O. Ivanova,List strong linear 2-arboricity of sparse graphs, J. Graph Theory, 67:2 (2011), 83-90. Zbl 1218.05038 · Zbl 1218.05038
[6] O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, A. Raspaud,Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at mostk, J. Graph Theory,65:2 (2010), 83-93. Zbl 1209.05177 · Zbl 1209.05177
[7] O.V. Borodin, A.V. Kostochka,Defective 2-colorings of sparse graphs, J. Comb. Theory, Ser. B,104:1 (2014), 72-80. Zbl 1282.05041 · Zbl 1282.05041
[8] O.V. Borodin, A. Kostochka, M. Yancey,On 1-improper 2-coloring of sparse graphs, Discrete Mathematics,313:22 (2013), 2638-2649. Zbl 1281.05060 · Zbl 1281.05060
[9] G. Chartrand, D.P. Geller, S. Hedetniemi,Graphs with forbidden subgraphs, J. Comb. Theory, Ser. B,10:1 (1971), 12-41. Zbl 0223.05101 · Zbl 0223.05101
[10] I. Choi, L. Esperet,Improper coloring of graphs on surfaces, J. Graph Theory,91:1 (2019), 16-34. Zbl 1418.05062 · Zbl 1418.05062
[11] I. Choi, A. Raspaud,Planar graphs with girth at least 5 are (3,5)-colorable, Discrete Math., 318:4 (2015), 661-667. Zbl 1305.05072 · Zbl 1305.05072
[12] L.J. Cowen, R.H. Cowen, D.R. Woodall,Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory,10:2 (1986), 187-195. Zbl 0596.05024 · Zbl 0596.05024
[13] W. Cushing, H.A. Kierstead,Planar graphs are 1-relaxed, 4-choosable, Eur. J. Comb.,31:5 (2010), 1385—1397. Zbl 1221.05077 · Zbl 1221.05077
[14] Z. Dvoˇr´ak, S. Norin,Islands in minor-closed classes. I. Bounded treewidth and separators, arXiv (2017) (https://arxiv.org/abs/1710.02727).
[15] H. Jiang, D. Yang,Decomposing a graph into forests: the nine dragon tree conjecture is true, Combinatorica,37:6 (2017), 1125—1137. Zbl 1399.05034 · Zbl 1399.05034
[16] A.N. Glebov,Splitting a planar graph of girth 5 into two forests with trees of small diameter, Discrete Math.,341:7 (2018), 2058—2067. Zbl 1387.05055 · Zbl 1387.05055
[17] A.N. Glebov, D.Zh. Zambalaeva,Partition of a planar graph with girth 6 into two forests with chain length at most 4, J. Appl. Ind. Math.,8:3 (2014), 317-328. Zbl 1324.05034 · Zbl 1324.05034
[18] H. Gr¨otzsch,Ein Dreifarbenzatz f¨ur dreikreisfreie Netze auf der Kugel, Math-Natur. Reih., 8(1959), 109-120. Zbl 0089.39506
[19] F. Havet, J.-S. Sereni,Improper choosability of graphs and maximum average degree, J. Graph Theory,52:3 (2006), 181-199. Zbl 1104.05026 · Zbl 1104.05026
[20] P. Haxell, T. Szab´o, G. Tardos,Bounded size components — partitions and transversals, J. Comb. Theory, Ser. B,88:2 (2003), 281—297. Zbl 1033.05083 · Zbl 1033.05083
[21] S.-J. Kim, A.V. Kostochka, D.B. West, H. Wu, X. Zhu,Decomposition of sparse graphs into forests and a graph with bounded degree, J. Graph Theory,74:3-4 (2013), 369-391. Zbl 1276.05092 · Zbl 1276.05092
[22] J. Kim, A. Kostochka, X. Zhu,Improper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs, Eur. J. Comb.,42:1 (2014), 26-48. Zbl 1297.05083 · Zbl 1297.05083
[23] J.M. Kleinberg, R. Motwani, P. Raghavan, S. Venkatasub-ramanian,Storage management for evolving databases, In 38th Annual Symposium on Foundations of Computer Science (FOCS’97), IEEE (1997), 353-362.
[24] N. Linial, J. Matouˇsek, O. Sheffet, G. Tardos,Graph colouring with no large monochromatic components, Comb. Probab. Comput.,17:4 (2008), 577—589. Zbl 1171.05021 · Zbl 1171.05021
[25] M. Montassier, P. Ochem,Near-colorings: Non-colorable graphs and NP-completeness, The Electron. J. Comb.,22:1 (2015). Zbl 1308.05052 · Zbl 1308.05052
[26] M. Montassier, P. Ossona de Mendez, A. Raspaud, X. Zhu,Decomposing a graph into forests, J. Comb. Theory, Ser. B,102:1 (2012), 38-52. Zbl 1237.05167 · Zbl 1237.05167
[27] B. Moore,An approximate version of the Strong Nine Dragon Tree Conjecture, arXiv (2019) (https://arxiv.org/abs/1909.07946).
[28] C.St.J.A. Nash-Williams,Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc., 36:1 (1961), 445-450. Zbl 0102.38805 · Zbl 0102.38805
[29] C.St.J.A. Nash-Williams,Decomposition of finite graphs into forests, J. Lond. Math. Soc., 39:1 (1964), 12. Zbl 0119.38805 · Zbl 0119.38805
[30] K.S. Poh,On the linear vertex-arboricity of a planar graph, J. Graph Theory,14:1 (1990), 73—75. Zbl 0705.05016 · Zbl 0705.05016
[31] R. ˇSkrekovski,List improper colorings of planar graphs with prescribed girth, Discrete Math., 214:1 (2000), 221-233. Zbl 0940.05027 · Zbl 0940.05027
[32] C. Thomassen,Every planar graph is 5-choosable, J. Comb. Theory, Ser. B,62:1 (1994), 180-181. Zbl 0805.05023 · Zbl 0805.05023
[33] M. Voigt,List colourings of planar graphs, Discrete Math.,120:1-3 (1993), 215-219. Zbl 0790.05030 · Zbl 0790.05030
[34] M. Voigt,A not 3-choosable planar graph without 3-cycles, Discrete Math.,146:1-3 (1995), 325-328. Zbl 0843.05034 · Zbl 0843.05034
[35] D.
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.