An approximate version of the tree packing conjecture

Böttcher, JuliaORCID logo; Hladký, Jan; Piguet, Diana; and Taraz, Anusch (2016) An approximate version of the tree packing conjecture. Israel Journal of Mathematics, 211 (1). pp. 391-446. ISSN 0021-2172
Copy

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 K(1+ε)n. This implies asymptotic versions of the Tree Packing Conjecture of Gy´arf´as 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.


picture_as_pdf
subject
Accepted Version

Download

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads