
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 K_{2,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 P_6. 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.
37 pages, 26 figures
Graph theory, 3-Decomposition Conjecture, Reducible Configurations, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Minimal Counterexample, 05C05, 05C38, 05C70
Graph theory, 3-Decomposition Conjecture, Reducible Configurations, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Minimal Counterexample, 05C05, 05C38, 05C70
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
