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

DOI10.1016/J.DAM.2020.01.016zbMATH Open1461.05159arXiv1806.11009OpenAlexW3003624629MaRDI QIDQ2663993FDOQ2663993

Authors: Elham Aboomahigir, Milad Ahanjideh, S. Akbari 

Publication date: 20 April 2021

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

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.

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

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

zbMATH Keywords

claw-free graphplanar graphsubcubic graphHoffmann-Ostenhof's conjecture4-chordal subcubic 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)

Cites Work

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

Cited In (7)

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

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)