The Loebl–Komlós–Sós Conjecture for Trees of Diameter $5$ and for Certain Caterpillars

Diana Piguet, Maya Jakobine Stein

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\in \Bbb N$, 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.


Full Text: PDF