An approximate version of the Loebl-Komlos-Sos conjecture

Author(s)

Piguet, Diana ^[1] ; Jakobine Stein, Maya ^[2]

Affiliation

^[1] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands - England

^[2] Univ Chile, Santiago - Chile

• Document type: Journal article
• Source: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 102, n. 1, p. 102-125, JAN 2012.
• Web of Science Citations: 9

Abstract

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)) <= k + m + o(k + m), as k + m -> infinity. (C) 2011 Elsevier Inc. All rights reserved. (AU)