Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite (Q2380453): Difference between revisions

Summary: By using the \textit{E. Szemerédi} regularity lemma [``Regular partitions of graphs,'' Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. int. CNRS No. 260, 399--401 (1978; Zbl 0413.05055)]; \textit{N. Alon} and \textit{B. Sudakov} [Electron. J. Comb. 13, No. 1, Research paper R19, 9 p. (2006; Zbl 1085.05036)] recently extended the classical \textit{B. Andrasfai}, \textit{P. Erdős} and \textit{V. T. Sós} theorem [Discrete Math. 8, 205--218 (1974; Zbl 0284.05106)] to cover general graphs. We prove, without using the Regularity Lemma, that tiic following stronger statement is true. Given any \((r+1)\)-partite graph \(H\) whose smallest part has \(t\) vertices, there exists a constant \(C\) such that for any given \(\varepsilon> 0\) and sufficiently large \(n\) the following is true. Whenever \(G\) is an \(n\)-vertex graph with minimum degree \[ \delta(G)\geq \Biggl(1-{3\over 3r-1}+ \varepsilon\Biggr)\,n, \] either \(G\) contains \(H\), or we can delete \(f(n,H)\leq Cn^{2-{1\over t}}\) edges from \(G\) to obtain an \(r\)-partite graph. Further, we are able to determine the correct order of magnitude of \(f(n,H)\) in terms of the Zarankiewicz extremal function.