2021/04/30 by Bachtler, Oliver, Heinrich, Irene · 1 citation
#05C05 #05C38 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2104.15113
The 3-decomposition conjecture is wide open. It asserts that every finite connected cubic graph can be decomposed into a spanning tree, a disjoint union of cycles, and a matching. We show that every such decomposition is derived from a homeomorphically irreducible spanning tree (HIST). This allows us to propose a novel reformulation of the 3-decomposition conjecture: the HIST-extension conjecture. We also prove that the following graphs are reducible configurations with respect to the 3-decomposition conjecture: the triangle, the K2,3, the Petersen graph with one vertex removed, the claw-square, the twin-house, and the domino. As an application, we show that all 3-connected graphs of tree-width at most 3 or of path-width at most 4 satisfy the 3-decomposition conjecture and that a 3-connected minimum counterexample to the conjecture is triangle-free, all cycles of length at most 6 are induced, and every edge is in the centre of an induced P6. Finally, we automate the naive part of the process of checking whether a configuration is reducible and we prove that all graphs of order at most 20 satisfy the 3-decomposition conjecture.