2026-07-24T23:36:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4718 2024-03-06T10:35:18Z ddc:004 open_access

An Approximate Version of the Tree Packing Conjecture via Random Embeddings Böttcher, Julia Hladký, Jan Piguet, Diana Taraz, Anusch tree packing conjecture Ringel’s conjecture random walks quasirandom graphs We prove that for any pair of constants a>0 and D and for n sufficiently large, every family of trees of orders at most n, maximum degrees at most D, and with at most n(n-1)/2 edges in total packs into the complete graph of order (1+a)n. This implies asymptotic versions of the Tree Packing Conjecture of Gyarfas from 1976 and a tree packing conjecture of Ringel from 1963 for trees with bounded maximum degree. A novel random tree embedding process combined with the nibble method forms the core of the proof. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julia Böttcher and Jan Hladký and Diana Piguet and Anusch Taraz 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.490 urn:nbn:de:0030-drops-47184 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.490 eng https://creativecommons.org/licenses/by/3.0/legalcode