On the Tree Packing Conjecture
József Balogh, Cory Palmer · SIAM Journal on Discrete Mathematics · 2013
The Gyárfás tree packing conjecture states that any set of $n-1$ trees $T_{1},T_{2},\dots, T_{n-1}$ such that $T_i$ has $n-i+1$ vertices packs into $K_n$ (for $n$ large enough). We show that $t=\frac{1}{10}n^{1/4}$ trees $T_1,T_2,\dots, T_t$ such that $T_i$ has $n-i+1$ vertices packs into $K_{n+1}$ (for $n$ large enough). We also prove that any set of $t=\frac{1}{10}n^{1/4}$ trees $T_1,T_2,\dots, T_t$ such that no tree is a star and $T_i$ has $n-i+1$ vertices packs into $K_{n}$ (for $n$ large enough). Finally, we prove that $t=\frac{1}{4}n^{1/3}$ trees $T_1,T_2,\dots, T_t$ such that $T_i$ has $n-i+1$ vertices packs into $K_n$ as long as each tree has maximum degree at least $2n^{2/3}$ (for $n$ large enough). One of the main tools used in the paper is the famous spanning tree embedding theorem of Komlós, Sárközy, and Szemerédi [Combin. Probab. Comput., 10 (2001), pp. 397--416].