On Erdős-Sós conjecture for trees of large size (Q276193): Difference between revisions

Summary: 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 [\textit{B. Zhou}, Acta Math. Sci. 4, 287--289 (1984; Zbl 0556.05019)], \(k+2\) vertices [\textit{P. J. Slater} et al., J. Graph Theory 9, No. 2, 213--216 (1985; Zbl 0574.05018)], \(k+3\) vertices [\textit{M. Woźniak}, J. Graph Theory 21, No. 2, 229--234 (1996; Zbl 0841.05017)] and \(k+4\) vertices [\textit{G. Tiner}, Ars Comb. 95, 143--150 (2010; Zbl 1249.05060)]. We further explore this direction. Given an arbitrary integer \(c\geqslant 1\), we prove Erdős-Sós conjecture in the case when \(G\) has \(k+c\) vertices provided that \(k\geqslant k_0(c)\) (here \(k_0(c)=c^{12}\mathrm{polylog}(c)\)). We also derive a corollary related to the Tree Packing Conjecture.