We study edge-decompositions of highly connected graphs into copies of a given tree. In particular we attack the following conjecture by Barát and Thomassen: for each tree $T$, there exists a natural number $k_T$ such that if $G$ is a $k_T$-edge-connected graph, and $|E(T)|$ divides $|E(G)|$, then $E(G)$ has a decomposition into copies of $T$. As one of our main results it is sufficient to prove the conjecture for bipartite graphs. The same result has been independently obtained by Carsten Thomassen (2013).Let $Y$ be the unique tree with degree sequence $(1,1,1,2,3)$. We prove that if $G$ is a $191$-edge-connected graph of size divisible by $4$, then $G$ has a $Y$-decomposition. This is the first instance of such a theorem, in which the tree is different from a path or a star. Recently Carsten Thomassen proved a more general decomposition theorem for bistars, which yields the same result with a worse constant.
@article{10_37236_2110,
author = {J\'anos Bar\'at and D\'aniel Gerbner},
title = {Edge-decomposition of graphs into copies of a tree with four edges},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/2110},
zbl = {1300.05243},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2110/}
}
TY - JOUR
AU - János Barát
AU - Dániel Gerbner
TI - Edge-decomposition of graphs into copies of a tree with four edges
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/2110/
DO - 10.37236/2110
ID - 10_37236_2110
ER -
%0 Journal Article
%A János Barát
%A Dániel Gerbner
%T Edge-decomposition of graphs into copies of a tree with four edges
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2110/
%R 10.37236/2110
%F 10_37236_2110
János Barát; Dániel Gerbner. Edge-decomposition of graphs into copies of a tree with four edges. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/2110
