2015/12/29 by Ferber, Asaf, Lee, Choongbum, Mousset, Frank · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1512.08701
Let \mathcal G be a separable family of graphs. Then for all positive constants ε and Δ and for every sufficiently large integer n, every sequence G1,\dotsc,Gt∈\mathcal G of graphs of order n and maximum degree at most Δ such that e(G1)+\dotsb+e(Gt) ≤ (1-ε)\binomn2 packs into Kn. This improves results of Böttcher, Hladký, Piguet, and Taraz when \mathcal G is the class of trees and of Messuti, Rödl, and Schacht in the case of a general separable family. The result also implies approximate versions of the Oberwolfach problem and of the Tree Packing Conjecture of Gyárfás (1976) for the case that all trees have maximum degree at most Δ. The proof uses the local resilience of random graphs and a special multi-stage packing procedure.