Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite (Q2380453): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0907.3815 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 05:14, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite |
scientific article |
Statements
Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite (English)
0 references
26 March 2010
0 references
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.
0 references