×

zbMATH — the first resource for mathematics

Partition of a planar graph with girth 6 into two forests with chain length at most 4. (Russian, English) Zbl 1324.05034
Diskretn. Anal. Issled. Oper. 21, No. 2, 33-51 (2014); translation in J. Appl. Ind. Math. 8, No. 3, 317-328 (2014).
Summary: We prove that the vertex set of every planar graph with girth at most 6 can be partitioned into two subsets each of which generates a forest in which the length of each chain does not exceed 4.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borodin, O V; Ivanova, A O, Near-proper vertex 2-colorings of sparse graphs, Diskretn. Anal. Issled. Oper., 16, 16-20, (2009) · Zbl 1249.05110
[2] Borodin, O V; Ivanova, A O, Partitioning sparse plane graphs into two induced subgraphs of small degree, Siberian Electronic Math. Rep., 6, 13-16, (2009) · Zbl 1299.05261
[3] Glebov, A N; Zambalaeva, D Zh, Path partitions of planar graphs, Siberian Electronic Math. Rep., 4, 450-459, (2007) · Zbl 1132.05315
[4] Zambalaeva, D Zh, A partition of a planar graph with girth 7 into two starlike forests, Diskretn. Anal. Issled. Oper., 16, 20-46, (2009) · Zbl 1249.05317
[5] Borodin, O; Ivanova, A, List strong linear 2-arboricity of sparse graphs, J. Graph Theory, 67, 83-90, (2011) · Zbl 1218.05038
[6] Borowiecki, M; Broere, I; Frick, M; Mihok, P; Semanisin, G, A survey of hereditary properties of graphs, Discus. Math., Graph Theory, 17, 5-50, (1997) · Zbl 0902.05026
[7] Broere, I; Dorfling, M; Dunbar, J E; Frick, M, A path(ological) partition problem, Discus. Math., Graph Theory, 18, 113-125, (1998) · Zbl 0912.05048
[8] Broere, I; Hajnal, P; Mihok, P; Semanisin, G, ’partition problems and kernels of graphs, Discus. Math., Graph Theory, 17, 311-313, (1997) · Zbl 0906.05059
[9] Mihok, J, Additive hereditary properties and uniquely partitionable graphs, 49-58, (1985), Zielona Gora · Zbl 0623.05043
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.