Proof of the bandwidth conjecture of Bollobás and Komlós
Böttcher, J.
, Schacht, M. & Taraz, A.
(2009).
Proof of the bandwidth conjecture of Bollobás and Komlós.
Mathematische Annalen,
343(1), 175-205.
https://doi.org/10.1007/s00208-008-0268-6
, Schacht, M. & Taraz, A.
(2009).
Proof of the bandwidth conjecture of Bollobás and Komlós.
Mathematische Annalen,
343(1), 175-205.
https://doi.org/10.1007/s00208-008-0268-6
Abstract
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.