An approximate version of the tree packing conjecture
Böttcher, J.
, Hladký, J., Piguet, D. & Taraz, A.
(2016).
An approximate version of the tree packing conjecture.
Israel Journal of Mathematics,
211(1), 391-446.
https://doi.org/10.1007/s11856-015-1277-2
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.
| ['eprint_fieldname_type' not defined] | ['eprint_typename_article' not defined] |
|---|---|
| Copyright holders | © 2016 Springer |
| Departments | LSE['lib/metafield:join_subject_parts' not defined]Academic Departments['lib/metafield:join_subject_parts' not defined]Mathematics |
| DOI | 10.1007/s11856-015-1277-2 |
| ['eprint_fieldname_datestamp' not defined] | 04 ['lib/utils:month_short_02' not defined] 2016 |
| Acceptance Date | 20 ['lib/utils:month_short_10' not defined] 2014 |
| URI | https://researchonline.lse.ac.uk/id/eprint/65240 |
Explore Further
- https://www.scopus.com/pages/publications/84953281806 (Scopus publication)
- http://www.springer.com/mathematics/journal/11856 (Official URL)
-
subject - ['content_typename_accepted' not defined]
Download this file
Share this file
ORCID: https://orcid.org/0000-0002-4104-3635