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
|
PDF
- Accepted Version
Download (779kB) | Preview |
Identification Number: https://doi.org/10.1007/s11856-015-1277-2
Abstract
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 |
|---|---|
| Official URL: | http://www.springer.com/mathematics/journal/11856 |
| Additional Information: | © 2016 Springer |
| Divisions: | Mathematics |
| Subjects: | Q Science > QA Mathematics |
| Date Deposited: | 04 Feb 2016 16:51 |
| Last Modified: | 20 Sep 2025 01:11 |
| Projects: | EP/J501414/1 |
| Funders: | Engineering and Physical Sciences Research Council, London Mathematical Society, University of Warwick |
| URI: | http://eprintstest.lse.ac.uk/id/eprint/65240 |
Actions (login required)
 |
View Item |
