2007/08/24 by Diana Piguet, Piguet, Diana, Maya Stein +2
Computer Science · Mathematics · #05C35 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C35
paper · pdf · doi:10.48550/arxiv.0708.3355
29 pages, 6 figures, referees' comments incorporated
openalex publication_date 2007/08/24 · arxiv created 2011/05/08 · arxiv updated 2011/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Loebl, Komlos, and Sos conjectured that if at least half of the vertices of a graph G have degree at least some natural number k, then every tree with at most k edges is a subgraph of G. Our main result is an approximate version of this conjecture for large enough n=|V(G)|, assumed that n=O(k). Our result implies an asymptotic bound for the Ramsey number of trees. We prove that r(Tk,Tm)≤ k+m+o(k+m),as k+m tends to infinity.