The Erdǒs-Sós Conjecture for Graphs WhoseComplements Contain No C4
Jian-huaYin, Jiong-shengLi · Acta Scientiarum Naturalium Universitatis Sunyatseni · 2004
Erdǒs and Sos conjectured in 1963 (see [1], Problem 12 in 247) that every graph G on n vertices with size e(G) > 1/2n(κ-1) contains every tree T of size k. In this paper, we prove the conjecture for graphs whose complements contain no cycles of length 4.