The Approximate Loebl--Komlós--Sós Conjecture IV: Embedding Techniques and the Proof of the Main Result

Jan Hladký, János Komlós, Diana Piguet, Miklós Simonovits, Maya Stein, Endre Szemerédi

Abstract

This is the last of a series of four papers in which we prove the following relaxation of the Loebl--Komlós--Sós 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 $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first two papers of this series, we decomposed the host graph $G$ and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure and proved that any graph satisfying the conditions of the above approximate version of the Loebl--Komlós--Sós conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations.

Locations

• SIAM Journal on Discrete Mathematics - View
• Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) - View - PDF
• arXiv (Cornell University) - View - PDF
• DataCite API - View