×

zbMATH — the first resource for mathematics

Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. (English) Zbl 1369.05169
Summary: An \((\mathcal{F},\mathcal{F}_d)\)-partition of a graph is a vertex-partition into two sets \(F\) and \(F_d\) such that the graph induced by \(F\) is a forest and the one induced by \(F_d\) is a forest with maximum degree at most \(d\). We prove that every triangle-free planar graph admits an \((\mathcal{F},\mathcal{F}_5)\)-partition. Moreover we show that if for some integer \(d\) there exists a triangle-free planar graph that does not admit an \((\mathcal{F},\mathcal{F}_d)\)-partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C07 Vertex degrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel, K.; Haken, W., Every planar map is four colorable. part 1: discharging, Illinois J. Math., 21, 429-490, (1977) · Zbl 0387.05009
[2] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable. part 2: reducibility, Illinois J. Math., 21, 491-567, (1977) · Zbl 0387.05010
[3] Borodin, O., A proof of grnbaum’s conjecture on the acyclic 5-colorability of planar graphs, Dokl. Akad. Nauk SSSR, 231, 1, 18-20, (1976), (in Russian)
[4] Borodin, O.; Glebov, A., On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph, Diskretnyi Analiz I Issledovanie Operatsii, 8, 4, 34-53, (2001), (in Russian) · Zbl 1012.05133
[5] Chartrand, G.; Kronk, H., The point-arboricity of planar graphs, J. Lond. Math. Soc., 1, 1, 612-616, (1969) · Zbl 0175.50505
[6] Grötzsch, H., Zur theorie der diskreten gebilde, VII, ein dreifarbensatz für dreikreisfreie netze auf der kugel, wiss. Z. martin-luther-universitat, halle-Wittenberg, math, Nat. Reihe, 8, 109-120, (1959)
[7] Montassier, M.; Ochem, P., Near-colorings: non-colorable graphs and NP-completeness, Electron. J. Combin., 22, 1, P1-57, (2015) · Zbl 1308.05052
[8] Poh, K., On the linear vertex-arboricity of a plane graph, J. Graph Theory, 14, 1, 73-75, (1990) · Zbl 0705.05016
[9] Raspaud, A.; Wang, W., On the vertex-arboricity of planar graphs, European J. Combin., 29, 4, 1064-1075, (2008) · Zbl 1144.05024
[10] Thomassen, C., Decomposing a planar graph into degenerate graphs, J. Combin. Theory Ser. B, 65, 2, 305-314, (1995) · Zbl 0840.05070
[11] Thomassen, C., Decomposing a planar graph into an independent set and a 3-degenerate graph, J. Combin. Theory Ser. B, 83, 2, 262-271, (2001) · Zbl 1024.05075
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.