Towards obtaining a 3-decomposition from a perfect matching (Q2094896)

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.