Back to Search Start Over

Perfectly packing graphs with bounded degeneracy and many leaves

Authors :
Allen, Peter
Böttcher, Julia
Clemens, Dennis
Taraz, Anusch
Publication Year :
2019

Abstract

We prove that one can perfectly pack degenerate graphs into complete or dense $n$-vertex quasirandom graphs, provided that all the degenerate graphs have maximum degree $o(\frac{n}{\log n})$, and in addition $\Omega(n)$ of them have at most $(1-\Omega(1))n$ vertices and $\Omega(n)$ leaves. This proves Ringel's conjecture and the Gy\'arf\'as Tree Packing Conjecture for all but an exponentially small fraction of trees (or sequences of trees, respectively).<br />Comment: 51 pages

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1906.11558
Document Type :
Working Paper