Packing degenerate graphs

Abstract

Given $D$ and $\gamma >0$, whenever $c>0$ is sufficiently small and $n$ sufficiently large, if $\mathcal{G}$ is a family of $D$-degenerate graphs of individual orders at most $n$, maximum degrees at most $\frac{cn}{\log n}$, and total number of edges at most $(1-\gamma )\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, then $\mathcal{G}$ packs into the complete graph $K_n$. Our proof proceeds by analysing a natural random greedy packing algorithm. This version of the manuscript corrects a small error that appeared in the published version [Adv Math, 354 (2019), 106739].

48 pages. This version corrects small errors that we found after the publication in Adv Math. More details in Section 1.1

References in corpus (7)

• The existence of designs
• An approximate version of the Tree Packing Conjecture
• Packing minor-closed families of graphs into complete graphs
• Fractional Clique Decompositions of Dense Graphs and Hypergraphs
• Hypergraph $F$-designs for arbitrary $F$
• Packing trees of unbounded degrees in random graphs
• Almost all trees are almost graceful

Cited by in corpus (4)

• Almost all trees are almost graceful
• Ringel's tree packing conjecture in quasirandom graphs
• The tree packing conjecture for trees of almost linear maximum degree
• Tree decompositions of graphs without large bipartite holes