Optimal packings of bounded degree trees

trees to have arbitrary degrees). Similarly, we show that Ringel's conjecture from 1963 holds for all bounded degree trees. We deduce these results from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs. Our proofs involve Szemer'{e}di's regularity lemma, results on Hamilton decompositions of robust expanders, random walks, iterative absorption as well as a recent blow-up lemma for approximate decompositions.

Review text

Summary: We prove that if \(T_1,\dots, T_n\) is a sequence of bounded degree trees such that \(T_i\) has \(i\) vertices, then \(K_n\) has a decomposition into \(T_1,\dots, T_n\). This shows that the tree packing conjecture of \textit{A. Gyarfas} and \textit{J. Lehel} [in: Combinatorics. Combinatorial colloquium held at Keszthely, Hungary, 1976. Vol. I and II. Amsterdam-Oxford-New York: North-Holland Publishing Company. 463--469 (1978; Zbl 0389.05030)] holds for all bounded degree trees (in fact, we can allow the first \(o(n)\) trees to have arbitrary degrees). Similarly, we show that Ringel's conjecture [``Problem 25, In: Theory of graphs and its applications: proceedings of the symposium held in Smolenice. Prague: Czechoslovak Academy of Sciences (1963)] holds for all bounded degree trees. We deduce these results from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs. Our proofs involve Szemerédi's regularity lemma, results on Hamilton decompositions of robust expanders, random walks, iterative absorption as well as a recent blow-up lemma for approximate decompositions.

Recommendations

Cites work

Cited in

(37)

This page was built for publication: Optimal packings of bounded degree trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279501)