# On the tree packing conjecture

On the tree packing conjecture - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: **
On the tree packing conjecture**

The Gy\arf\as tree packing conjecture states that any set of $n-1$ trees $T {1},T {2},

., T {n-1}$ such that $T i$ has $n-i+1$ vertices pack into $K n$. We show that $t=1-10n^{1-4}$ trees $T 1,T 2,

., T t$ such that $T i$ has $n-i+1$ vertices pack into $K {n+1}$ for $n$ large enough. We also prove that any set of $t=1-10n^{1-4}$ trees $T 1,T 2,

., T t$ such that no tree is a star and $T i$ has $n-i+1$ vertices pack into $K {n}$ for $n$ large enough. Finally, we prove that $t=1-4n^{1-3}$ trees $T 1,T 2,

., T t$ such that $T i$ has $n-i+1$ vertices pack 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\os, S\ark\-ozy and Szemer\edi.

Author: **József Balogh; Cory Palmer**

Source: https://archive.org/