The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
Artículo

Publication date
2017Metadata
Show full item record
Cómo citar
Hladký, Jan
Cómo citar
The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
Author
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 α > 0 there exists a number k0 such that for every k > k0, every n-vertex graph G with at least (1/2 + α)n vertices of degree at least (1 + α)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.
Indexation
Artículo de publicación SCOPUS
Identifier
URI: https://repositorio.uchile.cl/handle/2250/168897
DOI: 10.1137/140982878
ISSN: 08954801
Quote Item
SIAM Journal on Discrete Mathematics, Volumen 31, Issue 2, 2017, Pages 1072-1148
Collections