An approximate version of the Loebl-Komlós-Sós conjecture

Abstract

The LoeblKomlósSós conjecture states that, given a graph G and a natural number k, if at least half the vertices of G have degree at least k, then any tree with at most k edges is a subgraph of G. We prove an approximate version of this conjecture for large graphs and k linear in |V(G)|.

Keywords

• approximate
• version
• Loebl-Komlós-Sós
• conjecture