Tree packing conjectures; Graceful tree labeling conjecture

Honza Hladký

Abstract

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. We shall discuss