Number of the records: 1

# The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs

- 1.0474809 - MÚ 2018 RIV US eng J - Journal Article
**Hladký, Jan - Komlós, J. - Piguet, Diana - Simonovits, M. - Stein, M. - Szemerédi, E.**

The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs.*SIAM Journal on Discrete Mathematics*. Roč. 31, č. 2 (2017), s. 983-1016. ISSN 0895-4801. E-ISSN 1095-7146**R&D Projects**: GA MŠk(CZ) 1M0545**EU Projects**: European Commission(XE) 628974 - PAECIDM**Institutional support**: RVO:67985840 ; RVO:67985807**Keywords**: extremal graph theory * Loebl–Komlós–Sós conjecture * regularity lemma**OECD category**: Pure mathematics; Pure mathematics (UIVT-O)**Impact factor**: 0.717, year: 2017

http://epubs.siam.org/doi/10.1137/140982854

This is the second 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 $(0.5+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 this series, we gave a decomposition of the graph $G$ into several parts of different characteristics, this decomposition might be viewed as an analogue of a regular partition for sparse graphs. In the present paper, we find a combinatorial structure inside this decomposition. In the third and fourth papers, we refine the structure and use it for embedding the tree $T$.

**Permanent Link:**http://hdl.handle.net/11104/0271760

File Download Size Commentary Version Access Hladky3.pdf 7 1.1 MB Publisher’s postprint require

Number of the records: 1