An approximate version of the Loebl-Komlos-Sos conjecture

Autor(es)

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

Afiliação do(s) autor(es)

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

^[2] Univ Chile, Santiago - Chile

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 102, n. 1, p. 102-125, JAN 2012.
• Citações Web of Science: 9

Resumo

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)

• Processo FAPESP: 05/54051-9 - Problemas finitos e infinitos da teoria dos grafos e hipergrafos.
• Beneficiário: Maya Jakobine Stein
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado