Thin trees in 8-edge-connected planar graphs

DOI10.1016/J.IPL.2018.11.009MaRDI QIDQ1711432zbMATH OpenOpenAlexFDO

Authors Ramin Mousavi

Publication date 18 January 2019

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2018.11.009

zbMATH Keywords

algorithmdecompositionedge-coloringplanar graphthin tree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Recommendations

• Bounded diameter arboricity
• scientific article; zbMATH DE number 861354
• Decomposing a planar graph with girth at least 8 into a forest and a matching
• Decomposition of some planar graphs into trees
• Decomposing a planar graph with girth 9 into a forest and a matching

Cites work

• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Bounded diameter arboricity
• Decomposing a graph into forests
• Decomposing a planar graph with girth 9 into a forest and a matching
• Decomposing a planar graph with girth at least 8 into a forest and a matching
• The asymmetric traveling salesman problem on graphs with bounded genus

Cited in

(2)

• 8-shredders in 8-connected graphs
• Bounded diameter arboricity

This page was built for publication: Thin trees in 8-edge-connected planar graphs

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