| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652931 | Electronic Notes in Discrete Mathematics | 2007 | 5 Pages |
Abstract
The Loebl–Komlós–Só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)|.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
