The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs

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

Research output: Contribution to journalArticle

10 Scopus citations


This 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 α > 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 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.

Original languageEnglish (US)
Pages (from-to)1017-1071
Number of pages55
JournalSIAM Journal on Discrete Mathematics
Issue number2
StatePublished - 2017

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


  • Extremal graph theory
  • Graph decomposition
  • Loebl-Komlós-Sós conjecture
  • Regularity lemma
  • Sparse graph
  • Tree embedding

Fingerprint Dive into the research topics of 'The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs'. Together they form a unique fingerprint.

  • Cite this