Tree packing conjectures; Graceful tree labelling conjecture

Tree packing conjectures; Graceful tree labelling conjecture

Tue, 26/01/2010
14:30 		Jan Hladky (University of Warwick) Combinatorial Theory Seminar Add to calendar L3
Tree packing conjectures; Graceful tree labelling conjecture
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 Labelling conjecture for trees of bounded degree. In the talk we shall give proofs of both results. We shall discuss possible extensions thereof to trees of unbounded degree.