An approximate version of the Loebl-Komlos-Sos conjecture

Loebl, Komlos, and Sos conjectured that if at least half of the vertices of a graph G have degree at least some k is an element of N. 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 = vertical bar V(G)vertical bar, assumed that n = O (k). Our result implies an asymptotic bound for the Ramsey number of trees. We prove that r(T-k, T-m) infinity. (C) 2011 Elsevier Inc. All rights reserved.