The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars (Article No. R106)

Abstract

Loebl, Komlós, and Sós conjectured that if at least half the vertices of a graph G have degree at least some k, then every tree with at most k edges is a subgraph of G. We prove the conjecture for all trees of diameter at most 5 and for a class of caterpillars.

Our result implies a bound on the Ramsey number r(T,T') of trees T,T' from the above classes.

Keywords

• Loebl-Komlós-Sós
• conjecture
• trees
• diameter
• certain
• caterpillars
• Article