2024/03/15 by Janzer, Barnabás, Montgomery, Richard
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2403.10515
The famous tree packing conjecture of Gyárfás from 1976 says that any sequence of trees T1,…,Tn such that |Ti|=i for each i∈ [n] packs into the complete n-vertex graph Kn. Packing even just the largest trees in such a sequence has proven difficult, with Bollobás drawing attention to this in 1995 by conjecturing that, for each k, if n is sufficiently large then the largest k trees in any such sequence can be packed into Kn. This has only been shown for k≤ 5, by Żak, despite many partial results and much related work on the full tree packing conjecture. We prove Bollobás's conjecture, by showing that, moreover, a linear number of the largest trees can be packed in the tree packing conjecture.