Number of the records: 1  

The Approximate Loebl-Komlos-Sos Conjecture III: The Finer Structure of LKS Graphs

  1. 1.
    SYSNO ASEP0474830
    Document TypeJ - Journal Article
    R&D Document TypeJournal Article
    Subsidiary JČlánek ve WOS
    TitleThe Approximate Loebl-Komlos-Sos Conjecture III: The Finer Structure of LKS Graphs
    Author(s) Hladký, J. (DE)
    Komlós, J. (US)
    Piguet, Diana (UIVT-O) RID, ORCID, SAI
    Simonovits, M. (HU)
    Stein, M. (CL)
    Szemerédi, E. (HU)
    Source TitleSIAM Journal on Discrete Mathematics - ISSN 0895-4801
    Roč. 31, č. 2 (2017), s. 1017-1071
    Number of pages55 s.
    Languageeng - English
    CountryUS - United States
    Keywordsextremal graph theory ; Loebl–Komlós–Sós conjecture ; regularity lemma
    Subject RIVBA - General Mathematics
    OECD categoryPure mathematics
    R&D Projects1M0545 GA MŠk - Ministry of Education, Youth and Sports (MEYS)
    GJ16-07822Y GA ČR - Czech Science Foundation (CSF)
    Institutional supportUIVT-O - RVO:67985807
    UT WOS000404770300023
    EID SCOPUS85022094119
    DOI10.1137/140982866
    AnnotationThis is the third 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 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 fourth paper, the refined structure will be used for embedding the tree $T$.
    WorkplaceInstitute of Computer Science
    ContactTereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
    Year of Publishing2018
Number of the records: 1