On Erdős-Sós Conjecture for Trees of Large Size

Citations Over TimeTop 18% of 2016 papers

Abstract

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.

Related Papers

• → Eye Movements as a Probe of Corollary Discharge Function in Schizophrenia(2014)8 cited
• → A note on a corollary of Sard’s theorem(1975)4 cited
• → Corrigendum to “Strongly self-absorbing C*-dynamical systems”(2020)4 cited
• A Preliminary Probe into the Proving Method of a Geometry Theorem(2002)
• Study on Housing Corollary Construction Mode of Communication(2009)