pith. sign in

arxiv: 1404.0697 · v3 · pith:2X7AFNK2new · submitted 2014-04-02 · 🧮 math.CO

An approximate version of the Tree Packing Conjecture

classification 🧮 math.CO
keywords treeconjecturepackingdeltaepsilonmaximumtreesapproximate
0
0 comments X
read the original abstract

We prove that for any pair of constants $\epsilon>0$ and $\Delta$ and for $n$ sufficiently large, every family of trees of orders at most $n$, maximum degrees at most $\Delta$, and with at most $\binom{n}{2}$ edges in total packs into $K_{(1+\epsilon)n}$. This implies asymptotic versions of the Tree Packing Conjecture of Gyarfas 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.