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

DOI10.1016/J.JCTB.2018.05.006MaRDI QIDQ1633745zbMATH OpenOpenAlexWikidataFDO

Authors Kolja Knauer, Torsten Ueckerdt

Publication date 20 December 2018

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

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

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)

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.

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\)

Cites work

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

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)