Edge-decomposition of graphs into copies of a tree with four edges (Q405153): Difference between revisions

Summary: We study edge-decompositions of highly connected graphs into copies of a given tree. In particular we attack the following conjecture by \textit{J. Barát} and \textit{C. Thomassen} [J. Graph Theory 52, No. 2, 135--146 (2006; Zbl 1117.05088)]: 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 \textit{C. Thomassen} [J. Comb. Theory, Ser. B 103, No. 4, 504--508 (2013; Zbl 1301.05272)].{ }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 C. Thomassen [loc. cit.] proved a more general decomposition theorem for bistars, which yields the same result with a worse constant.