An approximate version of the Loebl-Komlós-Sós conjecture |
| |
Authors: | Diana Piguet Maya Jakobine Stein |
| |
Affiliation: | a School of Mathematics, University of Birmingham, United Kingdom b Universidad de Chile, Av. Blanco Encalada 2120, Santiago, Chile |
| |
Abstract: | Loebl, Komlós, and Sós conjectured that if at least half of the vertices of a graph G have degree at least some k∈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=|V(G)|, assumed that n=O(k).Our result implies an asymptotic bound for the Ramsey number of trees. We prove that r(Tk,Tm)?k+m+o(k+m), as k+m→∞. |
| |
Keywords: | Loebl-Komló s-Só s conjecture Extremal graph theory Median degree Tree |
本文献已被 ScienceDirect 等数据库收录! |
|