Constructing Trees in Graphs whose Complement has no K 2, s

Source abstract

We show that, if G is a graph of order n with maximal degree Δ( G ) and minimal degree δ( G ) whose complement contains no K 2, s , s [ges ] 2, then G contains every tree T of order n − s +1 whose maximal degree is at most Δ( G ) and whose vertex of second-largest degree is at most δ( G ). We then show that this result implies that special cases of two conjectures are true. We verify that the Erdös–Sós conjecture, which states that a graph whose average degree is larger than k −1 contains every tree of order k +1, is true for graphs whose complement does not contain a K 2,4 , and the Komlós–Sós conjecture, which states that every graph of median degree at least k contains every tree of order k +1, is true for graphs whose complement does not contain a K 2,3 .