Tree packing conjectures; Graceful tree labeling conjecture

Tree packing conjectures; Graceful tree labeling conjecture

-
Jan Hladky, University of Warwick
Fine Hall 224

A family of graphs $H_1,...,H_k$ packs into a graph $G$ if there exist pairwise edge-disjoint copies of $H_1,...,H_k$ in $G$. Gyarfas and Lehel conjectured that any family $T_1, ..., T_n$ of trees of respective orders $1, ..., n$ packs into $K_n$. A similar conjecture of Ringel asserts that $2n$ copies of any trees $T$ on $n+1$ vertices pack into $K_{2n+1}$.In a joint work with Boettcher, Piguet, Taraz we proved a theorem about packing trees. The theorem implies asymptotic versions of the above conjectures for families of trees of bounded maximum degree. Tree-indexed random walks controlled by the nibbling method are used in the proof. In a joint work with Adamaszek, Adamaszek, Allen and Grosu, we used the nibbling method to prove the approximate version of the related Graceful Tree Labeling conjecture for trees of bounded degree.
In the talk we shall give proofs of both results.