×

zbMATH — the first resource for mathematics

Splitting planar graphs of girth 6 into two linear forests with short paths. (English) Zbl 1367.05044
Summary: Recently, O. V. Borodin et al. [Discrete Math. 313, No. 22, 2638–2649 (2013; Zbl 1281.05060)] showed that the vertices of each planar graph of girth at least 7 can be 2-colored so that each color class induces a subgraph of a matching. We prove that any planar graph of girth at least 6 admits a vertex coloring in two colors such that each monochromatic component is a path of length at most 14. Moreover, we show a list version of this result. On the other hand, for each positive integer \(t\geq 3\), we construct a planar graph of girth 4 such that in any coloring of vertices in two colors there is a monochromatic path of length at least \(t\). It remains open whether each planar graph of girth 5 admits a 2-coloring with no long monochromatic paths.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C12 Distance in graphs
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Akiyama, Path chromatic numbers of graphs, J Graph Theory 13 (5) pp 569– (1989) · Zbl 0688.05024 · doi:10.1002/jgt.3190130506
[2] Alon, Partitioning into graphs with only small components, J Combin Theory Ser B 87 (2) pp 231– (2003) · Zbl 1023.05045 · doi:10.1016/S0095-8956(02)00006-0
[3] Appel, Every planar map is four colorable, Part I: Discharging, Illinois J Math 21 (3) pp 429– (1977) · Zbl 0387.05009
[4] Appel, Every planar map is four colorable, Part II: Reducibility, Illinois J Math 21 (3) pp 491– (1977) · Zbl 0387.05010
[5] Berke, Relaxed two-coloring of cubic graphs, J Combin Theory Ser B 97 (4) pp 652– (2007) · Zbl 1118.05029 · doi:10.1016/j.jctb.2006.12.001
[6] Berke, Deciding relaxed two-colourability: A hardness jump, Comb Probabi Comput 18 pp 53– (2009) · Zbl 1209.05071 · doi:10.1017/S0963548309009663
[7] Berman, A 4-color theorem for surfaces of genus g, Proc Am Math Soc 105 (2) pp 513– (1989) · Zbl 0672.05028
[8] Borodin, List strong linear 2-arboricity of sparse graphs, J Graph Theory 67 (2) pp 83– (2011) · Zbl 1218.05038 · doi:10.1002/jgt.20516
[9] Borodin, On 1-improper 2-coloring of sparse graphs, Discrete Math 313 (22) pp 2638– (2013) · Zbl 1281.05060 · doi:10.1016/j.disc.2013.07.014
[10] Chappell, Topics in Discrete Mathematics pp 435– (2006) · doi:10.1007/3-540-33700-8_21
[11] Chartrand, A generalization of the chromatic number, Math Proc Cambridge Phil Soc 64 pp 265– (1968) · Zbl 0173.26204 · doi:10.1017/S0305004100042808
[12] Chartrand, Graphs with forbidden subgraphs, J Combin Theory Ser B 10 (1) pp 12– (1971) · Zbl 0223.05101 · doi:10.1016/0095-8956(71)90065-7
[13] Cowen, Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency, J Graph Theory 10 (2) pp 187– (1986) · Zbl 0596.05024 · doi:10.1002/jgt.3190100207
[14] L. J. Cowen W. Goddard C. E. Jesurum Coloring with defect 1997 548 557 · Zbl 1321.05079
[15] Diestel, Graph Theory (2010) · Zbl 1204.05001 · doi:10.1007/978-3-642-14279-6
[16] Eaton, Defective list colorings of planar graphs, Bull Inst Combin Appl 25 pp 79– (1999) · Zbl 0916.05026
[17] Esperet, Colouring planar graphs with three colours and no large monochromatic components, Comb Probab Comp 23 pp 551– (2014) · Zbl 1334.05030 · doi:10.1017/S0963548314000170
[18] L. Esperet P. Ochem Islands in graphs on surfaces 30 1 2016 206 219 · Zbl 1329.05105
[19] Glebov, Partition of a planar graph with girth 6 into two forests with chain length at most 4, J Appl Indus Math 8 (3) pp 317– (2014) · Zbl 1324.05034 · doi:10.1134/S199047891403003X
[20] Goddard, Acyclic colorings of planar graphs, Discrete Math 91 (1) pp 91– (1991) · Zbl 0742.05041 · doi:10.1016/0012-365X(91)90166-Y
[21] Havet, Improper choosability of graphs and maximum average degree, J Graph Theory 52 (3) pp 181– (2006) · Zbl 1104.05026 · doi:10.1002/jgt.20155
[22] Haxell, Bounded size components-partitions and transversals, J Combin Theory Ser B 88 (2) pp 281– (2003) · Zbl 1033.05083 · doi:10.1016/S0095-8956(03)00031-5
[23] J. Kleinberg R. Motwani P. Raghavan S. Venkatasubramanian Storage management for evolving databases 1997 353 353
[24] Linial, Graph colouring with no large monochromatic components, Comb Probab Comput 17 pp 577– (2008) · Zbl 1171.05021 · doi:10.1017/S0963548308009140
[25] Montassier, Near-colorings: Non-colorable graphs and NP-completeness, Electron J Comb 22 (2015) · Zbl 1308.05052
[26] Poh, On the linear vertex-arboricity of a planar graph, J Graph Theory 14 (1) pp 73– (1990) · Zbl 0705.05016 · doi:10.1002/jgt.3190140108
[27] ┼ákrekovski, List improper colourings of planar graphs, Comb Probab Comput 8 (3) pp 293– (1999) · Zbl 0940.05031 · doi:10.1017/S0963548399003752
[28] P. Weiner Improper colourings of graphs 2014
[29] Wood, Defective choosability of graphs without small minors, Electron J Comb 16 (1) pp R92– (2009) · Zbl 1186.05060
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.