2007/12/20 by Diana Piguet, Piguet, Diana, Maya Stein +2
Computer Science · Mathematics · #05C05 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C05
paper · pdf · doi:10.48550/arxiv.0712.3382
11 pages, 1 figure
arxiv created 2007/12/20 · openalex publication_date 2007/12/20 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Loebl, Komlos, and Sos 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,F) of trees T, F from the above classes.