![](/files/happy5.png)
3-Decomposition Conjecture
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
We state the conjecture in a more precise manner:
Let be a connected cubic graph. Then
contains a spanning tree
, a
-regular subgraph
and a matching
(where only
and not
or
may be empty) such that
and
for every
with
.
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:
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ C $](/files/tex/05d3558ef52267cc1af40e658352d98883668ee3.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G-E(C) $](/files/tex/73b16846f8c84290e37da460f237c4b5b2123d2a.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ M $](/files/tex/3f02401f624e31ef8679d3c3628c1f310058f388.png)
![$ G-M=T $](/files/tex/40858114dee961c51d485eb140f45fcc0af6dd5c.png)
Note that every cycle 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 has a matching
such that
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.