Search Results

Documents authored by Hladký, Jan

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.490
An Approximate Version of the Tree Packing Conjecture via Random Embeddings

Authors: Julia Böttcher, Jan Hladký, Diana Piguet, and Anusch Taraz

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
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.
Cite as

Julia Böttcher, Jan Hladký, Diana Piguet, and Anusch Taraz. An Approximate Version of the Tree Packing Conjecture via Random Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 490-499, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{bottcher_et_al:LIPIcs.APPROX-RANDOM.2014.490,
  author =	{B\"{o}ttcher, Julia and Hladk\'{y}, Jan and Piguet, Diana and Taraz, Anusch},
  title =	{{An Approximate Version of the Tree Packing Conjecture via Random Embeddings}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{490--499},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.490},
  URN =		{urn:nbn:de:0030-drops-47184},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.490},
  annote =	{Keywords: tree packing conjecture, Ringel’s conjecture, random walks, quasirandom graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact