Decomposing planar cubic graphs

DOI10.1002/JGT.22234MaRDI QIDQ4581288zbMATH OpenOpenAlexFDO

Authors Arthur Hoffmann-Ostenhof, Tomáš Kaiser, Kenta Ozeki

Publication date 16 August 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

3-regular graphcubic graphdecompositionseparating cyclespanning tree

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We show that this conjecture holds for the class of connected plane cubic graphs.

Recommendations

• Decomposing plane cubic graphs
• Decomposition of cubic graphs with a 2-factor consisting of three cycles
• Towards obtaining a 3-decomposition from a perfect matching
• Decompositions of cubic traceable graphs
• Edge decomposition of connected claw-free cubic graphs

Cited in

(22)

• Deciding whether a planar graph has a cubic subgraph is NP-complete
• Decomposing graphs into a spanning tree, an even graph, and a star forest
• Decomposition of cubic graphs related to Wegner's conjecture
• Snarks with special spanning trees
• Towards obtaining a 3-decomposition from a perfect matching
• Decomposition of cubic graphs with a 2-factor consisting of three cycles
• Jones' conjecture in subcubic graphs
• Decompositions of cubic traceable graphs
• Homeomorphically irreducible spanning trees in hexangulations of surfaces
• Decompositions of graphs into trees, forests, and regular subgraphs
• Decomposing claw-free subcubic graphs and 4-chordal subcubic graphs
• Decomposing series-parallel graphs into paths of length 3 and triangles
• scientific article; zbMATH DE number 861398 (Why is no real title available?)
• Decomposing planar graphs into graphs with degree restrictions
• On algorithmic certification of graph structures
• On the structure of a smallest counterexample and a new class verifying the 2-decomposition conjecture
• Decomposition of 3-connected cubic graphs
• Hoffmann-Ostenhof's 3-decomposition conjecture
• Splitting cubic circle graphs
• The 3-decomposition conjecture of cubic graphs
• Edge decomposition of connected claw-free cubic graphs
• Decomposing plane cubic graphs

This page was built for publication: Decomposing planar cubic graphs

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