Spanning 3-colourable subgraphs of small bandwidth in dense graphs

摘要

A conjecture by Bollobas and Komlos states the following: For every, gamma > 0 and integers r >= 2 and Delta, there exists beta > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least (r-1/r + gamma)n and H is an r-chromatic graph with n vertices, bandwidth at most beta n and maximum degree at most Delta, then G contains a copy of H. This conjecture generalises several results concerning sufficient degree conditions for the containment of spanning subgraphs. We prove the conjecture for the case r = 3. (c) 2007 Elsevier Inc. All rights reserved.