Number of the records: 1
The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs
- 1.
SYSNO ASEP 0474809 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs Author(s) Hladký, Jan (MU-W) RID, SAI, ORCID
Komlós, J. (US)
Piguet, Diana (UIVT-O) RID, ORCID, SAI
Simonovits, M. (HU)
Stein, M. (CL)
Szemerédi, E. (HU)Source Title SIAM Journal on Discrete Mathematics. - : SIAM Society for Industrial and Applied Mathematics - ISSN 0895-4801
Roč. 31, č. 2 (2017), s. 983-1016Number of pages 34 s. Language eng - English Country US - United States Keywords extremal graph theory ; Loebl–Komlós–Sós conjecture ; regularity lemma Subject RIV BA - General Mathematics OECD category Pure mathematics Subject RIV - cooperation Institute of Computer Science - General Mathematics R&D Projects 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) Institutional support MU-W - RVO:67985840 ; UIVT-O - RVO:67985807 UT WOS 000404770300022 EID SCOPUS 85021890019 DOI 10.1137/140982854 Annotation 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$. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2018
Number of the records: 1