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

DOI10.1137/140982854MaRDI QIDQ5267993zbMATH OpenOpenAlexWikidataFDO

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

Publication date 14 June 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.3871, http://real.mtak.hu/74258/1/1408.3871v4.pdf

zbMATH Keywords

extremal graph theoryregularity lemmagraph decompositiontree embeddingsparse graphLoebl-Komlós-Sós conjecture

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: This is the second of a series of four papers in which we prove the following relaxation of the Loebl-Komlos--Sos 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; 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 last two papers, we refine the structure and use it for embedding the tree $T$.

Recommendations

• The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• An approximate version of the Loebl-Komlós-Sós conjecture

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 861349 (Why is no real title available?)
• scientific article; zbMATH DE number 881162 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• An approximate version of the Loebl-Komlós-Sós conjecture
• Embedding large subgraphs into dense graphs
• Loebl-Komlós-Sós conjecture: dense case
• Proof of the Loebl-Komlós-Sós conjecture for large, dense graphs
• Proof of the \((n/2 - n/2 - n/2)\) conjecture for large \(n\)
• The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition

Cited in

(15)

• Maximum and minimum degree conditions for embedding trees
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result
• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• Gaps in the saturation spectrum of trees
• Loebl-Komlós-Sós conjecture: dense case
• A version of the Loebl-Komlós-Sós conjecture for skew trees
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
• Embedding trees with maximum and minimum degree conditions
• Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
• A skew version of the Loebl-Komlós-Sós conjecture
• A Local Approach to the Erdös--Sós Conjecture

This page was built for publication: The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5267993)