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 IV: Embedding Techniques and the Proof of the Main Result
复制标题
近似Loebl-Komlós-Sós猜想四：嵌入技术和主要结果的证明
DOI：
10.1137/140982878
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
E. Szemerédi
中科院分区：
文献类型：
--
作者：
J. Hladký;J. Komlos;Diana Piguet;M. Simonovits;M. Stein;E. Szemerédi
这是一系列四篇论文中的最后一篇，其中我们证明了 Loebl--Komlos--Sos 猜想的以下松弛：对于每个 $\alpha>0$ 都存在一个数字 $k_0$，这样对于每个 $k>k_0$，每个 $n$ 顶点图 $G$ 至少有 $(\frac12+\alpha)n$ 个顶点，度数至少为 $(1+\alpha)k$ 包含每个阶数 $T$ 的树$k$ 作为子图。在本系列的前两篇论文中，我们分解了主图$G$，并在分解内部找到了合适的组合结构。在第三篇论文中，我们改进了这个结构，并证明任何满足上述 Loebl-Komlos-Sos 猜想近似版本条件的图都包含十种特定配置之一。在本文中，我们将树 $T$ 嵌入到十个配置中的每一个中。
This is the last 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 two papers of this series, we decomposed the host graph $G$ and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure and proved that any graph satisfying the conditions of the above approximate version of the Loebl--Komlos--Sos conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations.
近似 Loebl-Komlós-Sós 猜想 I：稀疏分解
DOI：
10.1137/140982842
发表时间：
--
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
J. Hladký;J. Komlós;D. Piguet;M. Simonovits;M. Stein;E. Szemerédi
通讯作者：
E. Szemerédi