Geodesic
Colouring planar graphs with bounded monochromatic components
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 513-520.

Voir la notice de l'article provenant de la source Math-Net.Ru

Borodin and Ivanova 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. Axenovich et al. 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 Jiang and Yang, and the Strong Nine Dragon Tree Conjecture partially confirmed by Kim et al. and Moore.
Keywords: planar graph, defective colouring, clustered colouring, list colouring, girth, maximum average degree, fractional arboricity, Nine Dragon Tree Theorem.
Mots-clés : forest decomposition 
@article{SEMR_2020_17_a66,
     author = {A. N. Glebov},
     title = {Colouring planar graphs with bounded monochromatic components},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {513--520},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a66/}
}
TY  - JOUR
AU  - A. N. Glebov
TI  - Colouring planar graphs with bounded monochromatic components
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 513
EP  - 520
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a66/
LA  - en
ID  - SEMR_2020_17_a66
ER  - 
%0 Journal Article
%A A. N. Glebov
%T Colouring planar graphs with bounded monochromatic components
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 513-520
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a66/
%G en
%F SEMR_2020_17_a66
A. N. Glebov. Colouring planar graphs with bounded monochromatic components. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 513-520. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a66/

[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 | DOI | MR | Zbl

[2] K. Appel, W. Haken, “Every planar map is four colorable. Part I: Discharging”, Ill. J. Math., 21:3 (1977), 429–490 | DOI | MR | Zbl

[3] K. Appel, W. Haken, “Every planar map is four colorable. Part II: Reducibility”, Ill. J. Math., 21:3 (1977), 491–567 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[5] O.V. Borodin, A.O. Ivanova, “List strong linear 2-arboricity of sparse graphs”, J. Graph Theory, 67:2 (2011), 83–90 | DOI | MR | Zbl

[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 most $k$”, J. Graph Theory, 65:2 (2010), 83–93 | DOI | MR | Zbl

[7] O.V. Borodin, A.V. Kostochka, “Defective 2-colorings of sparse graphs”, J. Comb. Theory, Ser. B, 104:1 (2014), 72–80 | DOI | MR | Zbl

[8] O.V. Borodin, A. Kostochka, M. Yancey, “On 1-improper 2-coloring of sparse graphs”, Discrete Mathematics, 313:22 (2013), 2638–2649 | DOI | MR | Zbl

[9] G. Chartrand, D.P. Geller, S. Hedetniemi, “Graphs with forbidden subgraphs”, J. Comb. Theory, Ser. B, 10:1 (1971), 12–41 | DOI | MR | Zbl

[10] I. Choi, L. Esperet, “Improper coloring of graphs on surfaces”, J. Graph Theory, 91:1 (2019), 16–34 | DOI | MR | Zbl

[11] I. Choi, A. Raspaud, “Planar graphs with girth at least 5 are (3,5)-colorable”, Discrete Math., 318:4 (2015), 661–667 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[13] W. Cushing, H.A. Kierstead, “Planar graphs are 1-relaxed, 4-choosable”, Eur. J. Comb., 31:5 (2010), 1385–1397 | DOI | MR | Zbl

[14] Z. Dvořák, S. Norin, Islands in minor-closed classes. I. Bounded treewidth and separators, 2017, arXiv: 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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[18] H. Grötzsch, “Ein Dreifarbenzatz für dreikreisfreie Netze auf der Kugel”, Math-Natur. Reih., 8 (1959), 109–120 | Zbl

[19] F. Havet, J.-S. Sereni, “Improper choosability of graphs and maximum average degree”, J. Graph Theory, 52:3 (2006), 181–199 | DOI | MR | Zbl

[20] P. Haxell, T. Szabó, G. Tardos, “Bounded size components — partitions and transversals”, J. Comb. Theory, Ser. B, 88:2 (2003), 281–297 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[23] J.M. Kleinberg, R. Motwani, P. Raghavan, S. Venkatasub-Ramanian, “Storage management for evolving databases”, 38th Annual Symposium on Foundations of Computer Science, FOCS'97, IEEE, 1997, 353–362 | DOI

[24] N. Linial, J. Matoušek, O. Sheffet, G. Tardos, “Graph colouring with no large monochromatic components”, Comb. Probab. Comput., 17:4 (2008), 577–589 | DOI | MR | Zbl

[25] M. Montassier, P. Ochem, “Near-colorings: Non-colorable graphs and NP-completeness”, The Electron. J. Comb., 22:1 (2015) | MR | Zbl

[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 | DOI | MR | Zbl

[27] B. Moore, An approximate version of the Strong Nine Dragon Tree Conjecture, 2019, arXiv: 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 | DOI | MR | Zbl

[29] C. St.J.A. Nash-Williams, “Decomposition of finite graphs into forests”, J. Lond. Math. Soc., 39:1 (1964), 12 | DOI | MR | Zbl

[30] K.S. Poh, “On the linear vertex-arboricity of a planar graph”, J. Graph Theory, 14:1 (1990), 73–75 | DOI | MR | Zbl

[31] R. Škrekovski, “List improper colorings of planar graphs with prescribed girth”, Discrete Math., 214:1 (2000), 221–233 | DOI | MR | Zbl

[32] C. Thomassen, “Every planar graph is 5-choosable”, J. Comb. Theory, Ser. B, 62:1 (1994), 180–181 | DOI | MR | Zbl

[33] M. Voigt, “List colourings of planar graphs”, Discrete Math., 120:1–3 (1993), 215–219 | DOI | MR | Zbl

[34] M. Voigt, “A not 3-choosable planar graph without 3-cycles”, Discrete Math., 146:1–3 (1995), 325–328 | DOI | MR | Zbl

[35] D.R. Woodall, “Defective choosability of graphs in surfaces”, Discuss. Math. Graph Theory, 31:3 (2011), 441–459 | DOI | MR | Zbl