Perfectly packing graphs with bounded degeneracy and many leaves

Abstract

We prove that one can perfectly pack degenerate graphs into complete or dense $n$-vertex quasirandom graphs, provided that all the degenerate graphs have maximum degree $o(\frac{n}{\log n})$, and in addition $\Omega (n)$ of them have at most $(1-\Omega (1))n$ vertices and $\Omega (n)$ leaves. This proves Ringel's conjecture and the Gyárfás Tree Packing Conjecture for all but an exponentially small fraction of trees (or sequences of trees, respectively).

51 pages