An approximate version of the tree packing conjecture

Publikationstyp
Journal Article
Date Issued
2016-02-01
Sprache
English
Author(s)
Böttcher, Julia  
Hladký, Jan  
Piguet, Diana  
Taraz, Anusch  
Institut
Mathematik E-10  
TORE-URI
http://hdl.handle.net/11420/5974
Journal
Israel journal of mathematics  
Volume
211
Issue
1
Start Page
391
End Page
446
Citation
Israel Journal of Mathematics 1 (211): 391-446 (2016-02-01)
Publisher DOI
10.1007/s11856-015-1277-2
Scopus ID
2-s2.0-84953281806
We prove that for any pair of constants ɛ > 0 and Δ and for n sufficiently large, every family of trees of orders at most n, maximum degrees at most Δ, and with at most (n2) edges in total packs into (Formula presented.). This implies asymptotic versions of the Tree Packing Conjecture of Gyárfás from 1976 and a tree packing conjecture of Ringel from 1963 for trees with bounded maximum degree. A novel random tree embedding process combined with the nibble method forms the core of the proof.