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.

Published
2008-08-18
Article Number
R106