Perfectly packing graphs with bounded degeneracy and many leaves

Publikationstyp
Journal Article
Date Issued
2023-06
Sprache
English
Author(s)
Allen, Peter  
Böttcher, Julia  
Clemens, Dennis  orcid-logo
Taraz, Anusch  
Institut
Mathematik E-10  
TORE-URI
http://hdl.handle.net/11420/14550
Journal
Israel journal of mathematics  
Volume
255
Issue
2
Start Page
501
End Page
579
Citation
Israel Journal of Mathematics 255 (2): 501-579 (2023-06)
Publisher DOI
10.1007/s11856-022-2447-7
Scopus ID
2-s2.0-85144959730
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).