An approximate version of the Loebl-Komlos-Sos conjecture

作者：Piguet Diana^*; Stein Maya Jakobine

来源：Journal of Combinatorial Theory - Series B, 2012, 102(1): 102-125.

DOI：10.1016/j.jctb.2011.05.002

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

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). %26lt;br%26gt;Our result implies an asymptotic bound for the Ramsey number of trees. We prove that r(T-k, T-m) %26lt;= k + m + o(k + m), as k + m -%26gt; infinity.

• 出版日期2012-1