The Erdös-Sós Conjecture for Spiders

2018/04/18 by Fan, Genghua, Hong, Yanmei, Liu, Qinghai · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1804.06567

Abstract

The Erdös-Sós conjecture states that if G is a graph with average degree more than k-1, then G contains every tree of k edges. A spider is a tree with at most one vertex of degree more than 2. In this paper, we prove that Erdös-Sós conjecture holds for all spiders.

Cited by

• On Turán problems for Berge forests

Related

• Advances on the Conjecture of Erdős-Sós for spiders
• A local approach to the Erdős-Sós conjecture
• Embedding Nearly Spanning Trees
• On the Erdos-Sos Conjecture for Graphs on n=k+4 Vertices
• Note on the connectivity keeping spiders in k-connected graphs