An approximate version of the tree packing conjecture
Böttcher, Julia
; 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
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.
| Item Type | Article |
|---|---|
| Departments | Mathematics |
| DOI | 10.1007/s11856-015-1277-2 |
| Date Deposited | 04 Feb 2016 16:51 |
| URI | https://researchonline.lse.ac.uk/id/eprint/65240 |
ORCID: https://orcid.org/0000-0002-4104-3635