Spanning 3-colourable subgraphs of small bandwidth in dense graphs
Böttcher, J.
, Schacht, M. & Taraz, A.
(2008).
Spanning 3-colourable subgraphs of small bandwidth in dense graphs.
Journal of Combinatorial Theory, Series B,
98(4), 752-777.
https://doi.org/10.1016/j.jctb.2007.11.005
, Schacht, M. & Taraz, A.
(2008).
Spanning 3-colourable subgraphs of small bandwidth in dense graphs.
Journal of Combinatorial Theory, Series B,
98(4), 752-777.
https://doi.org/10.1016/j.jctb.2007.11.005
A conjecture by Bollobás and Komlós states the following: For every γ>0 and integers r⩾2 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.