Proof of the tree packing conjecture for bounded degree trees
Formal Metadata
| Title | Proof of the tree packing conjecture for bounded degree trees |
|
| Title of Series | |
| Number of Parts | 24 |
| Author | |
| Contributors | |
| License | You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor. |
| Identifiers | |
| Publisher | |
| Release Date | |
| Language | |
Content Metadata
| Subject Area | |
| Genre | |
| Abstract | We prove that given any sequence of $n$ bounded degree trees so that the $j$th tree has $j$ vertices, the complete graph on $n$ vertices has a decomposition into these trees, if $n$ is large enough. This shows that the tree packing conjecture of Gyarfas and Lehel from 1976 holds for all bounded degree trees. An important ingredient is a new tool for constructing approximate decompositions of dense quasirandom graphs into bounded degree graphs (which can be viewed as an extension of the classical blow-up lemma of Komlos, Sarkozy and Szemeredi to the setting of approximate decompositions). |
|
| Keywords | |