Towards obtaining a 3-decomposition from a perfect matching

DOI10.37236/11128MaRDI QIDQ2094896zbMATH OpenOpenAlexFDO

Authors Oliver Bachtler, Sven O. Krumke

Publication date 8 November 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cubic graphsgraph decompositionHoffmann-Ostenhof's conjecture

Mathematics Subject Classification ID

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

Review text

The 3-decomposition conjecture of Hoffmann-Ostenhof states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph, and a matching. This conjecture is known to be true for a special kind of cubic graphs, which includes planar cubic graphs (see [\textit{A. Hoffmann-Ostenhof} et al., J. Graph Theory 88, No. 4, 631--640 (2018; Zbl 1393.05210)]), claw-free cubic graphs (see [\textit{E. Aboomahigir} et al., Discrete Appl. Math. 296, 52--55 (2021; Zbl 1461.05159)]), and cubic Hamiltonian graphs (see [\textit{S. Akbari} et al., Discrete Math. 338, No. 8, 1322--1327 (2015; Zbl 1310.05167)]). In this article, the authors prove the 3-decomposition conjecture for a new class of graphs that generalize cubic Hamiltonian graphs, which they call star-like: A cubic graph \(G\) is star-like if it has a perfect matching \(M\) and the graph \(G_M\), which results from \(G\) by contracting all connected components of \(G-M\), is a star. For a cubic graph \(G\) with a perfect matching \(M\), every vertex of \(G-M\) has degree two and therefore \(G-M\) is a union of disjoint cycles. This means that vertices of \(G_M\) correspond to cycles of \(G-M\) and edges of \(G_M\) to edges of \(M\) connecting distinct cycles of \(G-M\). The authors observe that every cubic Hamiltonian graph is star-like. Namely, if \(C\) is a Hamiltonian cycle in a cubic graph \(G\), then the edge set of \(G-C\) forms a perfect matching \(M\) as every vertex in \(G-C\) has degree one. With such a perfect matching \(M\) the graph \(G-M\) consists of exactly one cycle and thus \(G_M\) is a graph with a single vertex and no edges, which is a star. They prove that star-like cubic graphs admit a 3-decomposition by constructing special kinds of decompositions for the central cycle in a star-like graph and extending these decompositions by adding the vertices of the outer cycles. Finally, they prove their main result: Every star-like cubic graph has a 3-decomposition. Afterwards, they construct an infinite family of star-like graphs that were not known to have a 3-decomposition before. They conclude with the natural question of whether the techniques developed in this paper could be used to prove the 3-decomposition conjecture for cubic graphs with a perfect matching \(M\) such that \(G_M\) is a tree and not necessarily a star.

Recommendations

• Decomposition of cubic graphs with a 2-factor consisting of three cycles
• Decomposing planar cubic graphs
• Decomposing plane cubic graphs
• scientific article; zbMATH DE number 6303054
• Edge decomposition of connected claw-free cubic graphs

Cites work

• Additivity of the genus of a graph
• Blocks and the nonorientable genus of graphs
• Covering Multigraphs by Simple Circuits
• Covering planar graphs with forests
• Covering planar graphs with forests, one having bounded maximum degree
• Cubic maximal nontraceable graphs
• Decomposing a planar graph with girth at least 8 into a forest and a matching
• Decomposing claw-free subcubic graphs and 4-chordal subcubic graphs
• Decomposing graphs into a spanning tree, an even graph, and a star forest
• Decomposing planar cubic graphs
• Decomposing plane cubic graphs
• Decomposition of cubic graphs with a 2-factor consisting of three cycles
• Decompositions of cubic traceable graphs
• Decompositions of graphs into trees, forests, and regular subgraphs
• Edge decomposition of connected claw-free cubic graphs
• Edge-partitions of planar graphs and their game coloring numbers
• Fulkerson's conjecture and circuit covers
• scientific article; zbMATH DE number 3643299 (Why is no real title available?)
• scientific article; zbMATH DE number 3937197 (Why is no real title available?)
• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• On graph decomposition: Hajós' conjecture, the clustering coefficient and dominating sets
• Research problems from the BCC22
• Smallest maximally nonhamiltonian graphs

Cited in

(8)

• Decomposition of cubic graphs with a 2-factor consisting of three cycles
• Decompositions of cubic traceable graphs
• Decomposing planar cubic graphs
• Towards obtaining a 3-Decomposition from a perfect Matching
• 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
• Decomposing plane cubic graphs

This page was built for publication: Towards obtaining a 3-decomposition from a perfect matching

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