Loebl-Komlos-Sos Conjecture: dense case

Abstract

We prove a version of the Loebl-Komlos-Sos Conjecture for dense graphs. For each q>0 there exists a number $n_0\in \mathbb{N}$ such that for any n>n_0 and k>qn the following holds: if G be a graph of order n with at least n/2 vertices of degree at least k, then any tree of order k+1 is a subgraph of G.

56 pages, 8 figures; substantial changes as suggested by a referee

References in corpus (4)

• The approximate Loebl-Komlós-Sós Conjecture IV: Embedding techniques and the proof of the main result
• The approximate Loebl-Komlos-Sos conjecture and embedding trees in sparse graphs
• An approximate version of the Loebl-Komlos-Sos conjecture
• The Loebl-Komlos-Sos conjecture for trees of diameter 5 and for certain caterpillars

Cited by in corpus (7)

• The approximate Loebl-Komlós-Sós Conjecture IV: Embedding techniques and the proof of the main result
• A Variant of the Erdős-Sós Conjecture
• The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs
• The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition
• The Approximate Loebl-Komlós-Sós Conjecture III: The finer structure of LKS graphs
• The approximate Loebl-Komlos-Sos conjecture and embedding trees in sparse graphs
• Maximum and minimum degree conditions for embedding trees