We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

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
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
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