Packing minor-closed families of graphs into complete graphs

Abstract

Motivated by a conjecture of Gyárfás, recently Böttcher, Hladký, Piguet, and Taraz showed that every collection $T_1,\dots ,T_t$ of trees on $n$ vertices with ${\sum }_{i=1}^{t}e(T_i)\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and with bounded maximum degree, can be packed into the complete graph on $(1+o(1))n$ vertices. We generalise this result where we relax the restriction of packing families of trees to families of graphs of any given non-trivial minor-closed class of graphs.

21 pages, accepted for publication in Journal of Combinatorial Theory, Series B

Cited by in corpus (8)

• Extremal density for sparse minors and subdivisions
• Packing degenerate graphs
• Packing trees of unbounded degrees in random graphs
• Almost all trees are almost graceful
• Ringel's tree packing conjecture in quasirandom graphs
• A blow-up lemma for approximate decompositions
• Tree decompositions of graphs without large bipartite holes
• The tree packing conjecture for trees of almost linear maximum degree