The Approximate Loebl-Komlós-Sós Conjecture III: The finer structure of LKS graphs

Abstract

This is the third of a series of four papers in which we prove the following relaxation of the Loebl-Komlos-Sos Conjecture: For every $\alpha >0$ there exists a number $k_0$ such that for every $k>k_0$ every $n$-vertex graph $G$ with at least $(\frac{1}{2}+\alpha )n$ vertices of degree at least $(1+\alpha )k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of the series, we gave a decomposition of the graph $G$ into several parts of different characteristics. In the second paper, we found a combinatorial structure inside the decomposition. In this paper, we will give a refinement of this structure. In the forthcoming fourth paper, the refined structure will be used for embedding the tree $T$.

59 pages, 4 figures; further comments by a referee incorporated; this includes a subtle but important fix to Lemma 5.1; as a consequence, Preconfiguration Clubs was changed

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-Komlós-Sós Conjecture I: The sparse decomposition
• The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs
• The Approximate Loebl-Komlós-Sós Conjecture III: The finer structure of LKS graphs

Cited by in corpus (6)

• 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