Ringel's tree packing conjecture in quasirandom graphs

Abstract

We prove that any quasirandom graph with $n$ vertices and $rn$ edges can be decomposed into $n$ copies of any fixed tree with $r$ edges. The case of decomposing a complete graph establishes a conjecture of Ringel from 1963.

45 pages, 5 figures

References in corpus (10)

• The existence of designs
• The existence of designs II
• Decompositions into spanning rainbow structures
• An approximate version of the Tree Packing Conjecture
• Packing minor-closed families of graphs into complete graphs
• Pseudorandom hypergraph matchings
• Hypergraph $F$-designs for arbitrary $F$
• Packing degenerate graphs
• Packing trees of unbounded degrees in random graphs
• Almost all trees are almost graceful