Home » Subject » Graph Theory

3-Decomposition Conjecture

Importance: High ✭✭✭
Author(s): Arthur
Hoffmann-Ostenhof
Subject: Graph Theory
Keywords: cubic graph
Recomm. for undergrads: no
Posted by: arthur
on: January 24th, 2017
Conjecture   (3-Decomposition Conjecture) Every connected cubic graph $ G $ has a decomposition into a spanning tree, a family of cycles and a matching.

We state the conjecture in a more precise manner:

Let $ G $ be a connected cubic graph. Then $ G $ contains a spanning tree $ H_1 $, a $ 2 $-regular subgraph $ H_2 $ and a matching $ H_3 $ (where only $ H_3 $ and not $ H_1 $ or $ H_2 $ may be empty) such that $ E(H_1) \cup E(H_2) \cup E(H_3) = E(G) $ and $ E(H_i) \cap E(H_j) =\emptyset $ for every $ \{i,j\} \subseteq \{1,2,3\} $ with $ i\not=j $.

The conjecture holds for all hamiltionian cubic graphs and for all connected planar cubic graphs, see [1] and see also [7].

Every cubic graph G which has a spanning tree T such that every vertex of T has degree three or one (such spanning tree T is called a HIST) obviously satisfies this conjecture. But not every connected cubic graph has a HIST, see [2].

The 3-Decomposition Conjecture has been shown to be equivalent to the following conjecture:

Conjecture  (2-Decomposition Conjecture) Let $ G $ be connected graph where every vertex has degree two or three. Suppose that for every cycle $ C $ of $ G $, $ G-E(C) $ is disconnected, then $ G $ has a decomposition into a spanning tree $ T $ and a matching $ M $, i.e $ G-M=T $.

Note that every cycle $ C $ which passes through a vertex of degree two satisfies the condition that G-E(C) is disconnected.

Remark: The 3-Decomposition Conjecture has also been shown to hold for other classes of cubic graphs, see for instance [3,4]. A survey on the 3-Decompostion conjecture has been given by the author 2015 in Pilsen (at that time the planar case was still open) see iti.zcu.cz/plzen15/talks/1-2a-Arthur-Survey_decomposition.ppt (and press play if you find the play button). Note that there are several papers on the problem whether a planar graph $ G $ has a matching $ M $ such that $ G-M $ is acyclic, see for instance [6].

Bibliography

[1] Arthur Hoffmann-Ostenhof, Tomáš Kaiser, Kenta Ozeki, \arXiv[Decomposing planar cubic graphs] 1609.05059 [math.CO]
[2] Arthur Hoffmann-Ostenhof, Kenta Ozeki, \arXiv[On HISTs in Cubic Graphs] 1507.07689 [math.CO]
[3] F. Abdolhosseini, S. Akbari, H. Hashemi, M.S. Moradian, \arXiv[Hoffmann-Ostenhof's conjecture for traceable cubic graphs] 1607.04768[math.CO]
[4] Anna Bachstein, Dong Ye (talk): www.rwoodroofe.math.msstate.edu/workshop2014/bachstein_slides.pdf
[5] Arthur Hoffmann-Ostenhof (talk): www.iti.zcu.cz/plzen15/talks/1-2a-Arthur-Survey_decomposition.ppt
[6] Yingqian Wang, Qijun Zhang, Discrete Mathematics 311 (2011) 844–849, Decomposing a planar graph with girth at least 8 into a forest and a matching
[7] Kenta Ozeki, Dong Ye, Decomposing plane cubic graphs, European Journal of Combinatorics 52 (2016) 40-46.


* indicates original appearance(s) of problem.
add new comment