Decomposing 4-connected planar triangulations into two trees and one path

DOI10.1016/J.JCTB.2018.05.006zbMATH Open1402.05176arXiv1710.02411OpenAlexW2962877123WikidataQ129801585 ScholiaQ129801585MaRDI QIDQ1633745FDOQ1633745

Authors: Kolja Knauer, Torsten Ueckerdt 

Publication date: 20 December 2018

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Refining a classical proof of Whitney, we show that any $4$-connected planar triangulation can be decomposed into a Hamiltonian path and two trees. Therefore, every $4$-connected planar graph decomposes into three forests, one having maximum degree at most $2$. We use this result to show that any Hamiltonian planar triangulation can be decomposed into two trees and one spanning tree of maximum degree at most $3$. These decompositions improve the result of Gonc{c}alves [Covering planar graphs with forests, one having bounded maximum degree. J. Comb. Theory, Ser. B, 100(6):729--739, 2010] that every planar graph can be decomposed into three forests, one of maximum degree at most $4$. We also show that our results are best-possible.

Full work available at URL: https://arxiv.org/abs/1710.02411

Recommendations

• Decompositions of quadrangle-free planar graphs
• Hamilton cycles in plane triangulations
• Decomposition of some planar graphs into trees
• Decomposing series-parallel graphs into paths of length 3 and triangles
• Decomposition of planar graphs without 5-cycles or \(K_4\)

zbMATH Keywords

planar graphsdecomposition into trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Edge-Disjoint Spanning Trees of Finite Graphs
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• Covering planar graphs with forests, one having bounded maximum degree
• Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
• Covering planar graphs with forests
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Edge-partitions of planar graphs and their game coloring numbers
• Decomposing a planar graph with girth at least 8 into a forest and a matching
• Decomposing a graph into forests
• Decomposition of sparse graphs, with application to game coloring number
• Floorplanning by graph dualization: \(L\)-shaped modules
• The incidence game chromatic number of \((a,d)\)-decomposable graphs
• Spectral radius of finite and infinite planar graphs and of graphs of bounded genus
• Covering a graph by forests and a matching

Cited In (2)

• The interval number of a planar graph is at most three
• Tree decompositions for a class of graphs

This page was built for publication: Decomposing 4-connected planar triangulations into two trees and one path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633745)