Decomposing claw-free subcubic graphs and 4-chordal subcubic graphs

DOI10.1016/J.DAM.2020.01.016MaRDI QIDQ2663993zbMATH OpenOpenAlexFDO

Authors Elham Aboomahigir, Milad Ahanjideh, S. Akbari

Publication date 20 April 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

4-chordal subcubic graphclaw-free graphHoffmann-Ostenhof's conjectureplanar graphsubcubic graph

Mathematics Subject Classification ID

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

Abstract: Hoffmann-Ostenhof's Conjecture states that the edge set of every connected cubic graph can be decomposed into a spanning tree, a matching and a $2$-regular subgraph. In this paper, we show that the conjecture holds for claw-free subcubic graphs and $4$-chordal subcubic graphs.

Recommendations

• Edge decomposition of connected claw-free cubic graphs
• Decomposing plane cubic graphs
• Decompositions of graphs into trees, forests, and regular subgraphs
• Decomposition of cubic graphs with a 2-factor consisting of three cycles
• Decomposing planar cubic graphs

Cites work

• Decomposing planar cubic graphs
• Decomposing plane cubic graphs
• Decompositions of graphs into trees, forests, and regular subgraphs
• Research problems from the BCC22

Cited in

(9)

• Towards obtaining a 3-decomposition from a perfect matching
• Decompositions of graphs into trees, forests, and regular subgraphs
• Some results on the reconstruction problems. p‐claw‐free, chordal, and p₄‐reducible graphs
• On the structure of a smallest counterexample and a new class verifying the 2-decomposition conjecture
• Hoffmann-Ostenhof's 3-decomposition conjecture
• The 3-decomposition conjecture of cubic graphs
• Edge decomposition of connected claw-free cubic graphs
• Decomposing plane cubic graphs
• Claw-free graphs. IV: Decomposition theorem

This page was built for publication: Decomposing claw-free subcubic graphs and 4-chordal subcubic graphs

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