Perfectly packing graphs with bounded degeneracy and many leaves
Allen, P.
, Böttcher, J., Clemens, D. & Taraz, A.
(2022).
Perfectly packing graphs with bounded degeneracy and many leaves.
Israel Journal of Mathematics,
https://doi.org/10.1007/s11856-022-2447-7
, Böttcher, J., Clemens, D. & Taraz, A.
(2022).
Perfectly packing graphs with bounded degeneracy and many leaves.
Israel Journal of Mathematics,
https://doi.org/10.1007/s11856-022-2447-7
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(Formula Presented.)., and in addition Ω(n) of them have at most (1 − Ω(1))n vertices and Ω(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).