Erdős and Sós conjectured that every graph $G$ of average degree greater than $k-1$ contains every tree of size $k$. Several results based upon the number of vertices in $G$ have been proved including the special cases where $G$ has exactly $k+1$ vertices (Zhou), $k+2$ vertices (Slater, Teo and Yap), $k+3$ vertices (Woźniak) and $k+4$ vertices (Tiner). We further explore this direction. Given an arbitrary integer $c\geq 1$, we prove Erdős-Sós conjecture in the case when $G$ has $k+c$ vertices provided that $k\geq k_0(c)$ (here $k_0(c)=c^{12}{\rm polylog}(c)$). We also derive a corollary related to the Tree Packing Conjecture.
@article{10_37236_5405,
author = {Agnieszka Goerlich and Andrzej \.Zak},
title = {On {Erd\H{o}s-S\'os} conjecture for trees of large size},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {1},
doi = {10.37236/5405},
zbl = {1335.05093},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5405/}
}
TY - JOUR
AU - Agnieszka Goerlich
AU - Andrzej Żak
TI - On Erdős-Sós conjecture for trees of large size
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/5405/
DO - 10.37236/5405
ID - 10_37236_5405
ER -
%0 Journal Article
%A Agnieszka Goerlich
%A Andrzej Żak
%T On Erdős-Sós conjecture for trees of large size
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/5405/
%R 10.37236/5405
%F 10_37236_5405
Agnieszka Goerlich; Andrzej Żak. On Erdős-Sós conjecture for trees of large size. The electronic journal of combinatorics, Tome 23 (2016) no. 1. doi: 10.37236/5405
