Proof of the bandwidth conjecture of Bollobás and Komlós
Proof of the bandwidth conjecture of Bollobás and Komlós
复制标题
Bollobás 和 Komlós 带宽猜想的证明
DOI：
10.1007/s00208-008-0268-6
复制
发表时间：
2009
影响因子：
1.4
通讯作者：
A. Taraz
中科院分区：
文献类型：
--
作者：
Julia Böttcher;M. Schacht;A. Taraz
本文用Bollobás和Komlós证明了以下猜想：对于每一个γ > 0和整数r≥1和Δ，存在具有以下性质的β > 0。如果G是一个足够大的图，有n个顶点，最小度至少为（(r−1)/r + γ）n， H是一个r色图，有n个顶点，带宽最多为βn，最大度最多为Δ，则G包含H的一个副本。
In this paper we prove the following conjecture by Bollobás and Komlós: For every γ > 0 and integers r ≥ 1 and Δ, there exists β > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r − 1)/r + γ)n and H is an r-chromatic graph with n vertices, bandwidth at most βn and maximum degree at most Δ, then G contains a copy of H.
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus