Spanning 3-colourable subgraphs of small bandwidth in dense graphs (Q933679): Difference between revisions

The bandwidth of a graph \(G\) of order \(n\) is \(b\) if \(b\) is the smallest positive integer such that the vertices of \(G\) can be labeled with \(\{1, 2, \cdots, n\}\) such that each edge \(ij\) of \(G\) satisfies \(| i - j| \leq b\). It was conjectured by Bollobás and \textit{J. Komlós} [see Comb. Probab. Comput. 8, No.1--2, 161--176 (1999; Zbl 0927.05041)] that given \(\gamma > 0\), every \(r\)-chromatic graph \(H\) of order \(n\) with bounded degree and bandwidth bounded by \(o(n)\) can be embedded in graph \(G\) of order \(n\) with \(\delta(G) \geq ((r-1)/r + \gamma)n\). The authors verify the conjecture in the case when \(r = 3\). More specifically, they prove given a positive integer \(\Delta\) and \(\gamma > 0\), there exists constants \(\beta > 0\) and \(N_0\), such that if \(n > N_0\), then if \(H\) is a \(3\)-chromatic graph of order \(n\) with \(\Delta(H) \leq \Delta\) and bandwidth at most \(\beta n\), and if \(G\) is a graph of order \(n\) with \(\delta(G) \geq (2/3 + \gamma)n\), then \(G\) contains a copy of \(H\). The proof uses Szemerédi's regularity lemma. It is also noted by the authors that the proof can be used to establish an \(O(n^{3.376})\) algorithm to embed the graph \(H\) into \(G\).