An approximate version of the Loebl-Komlos-Sos conjecture

Diana Piguet, M Jakobine Stein

Research output: Contribution to journalArticle

15 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)102-125
Number of pages24
JournalJournal of Combinatorial Theory. Series B
Issue number1
Publication statusPublished - 1 Jan 2012


  • Extremal graph theory
  • Median degree
  • Tree
  • Loebl-Komlos-Sos conjecture


Dive into the research topics of 'An approximate version of the Loebl-Komlos-Sos conjecture'. Together they form a unique fingerprint.

Cite this