# The Library

### Dense H-free graphs are almost (Χ(H)-1)-partite

Tools

Allen, Peter.
(2010)
*Dense H-free graphs are almost (Χ(H)-1)-partite.*
Electronic Journal of Combinatorics, Vol.17
(No.1:R21).
ISSN 1097-1440

PDF
WRAP_Allen_Dense_h-Free_Graphs.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (199Kb) |

Official URL: http://www.combinatorics.org/index.html

## Abstract

By using the Szemeredi Regularity Lemma, Alon and Sudakov recently

extended the classical Andrasfai-Erdos-Sos theorem to cover general graphs. We

prove, without using the Regularity Lemma, that the 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 ε>0 and sufficiently large n the following is

true. Whenever G is an n-vertex graph with minimum degree

δ(G)≥(1 −

3/3r−1 + ε)n,

either G contains H, or we can delete f(n,H)≤Cn2−1/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.

Item Type: | Journal Article |
---|---|

Subjects: | Q Science > QA Mathematics |

Divisions: | Faculty of Science > Mathematics |

Library of Congress Subject Headings (LCSH): | Graph theory |

Journal or Publication Title: | Electronic Journal of Combinatorics |

Publisher: | Electronic Journal of Combinatorics |

ISSN: | 1097-1440 |

Official Date: | 29 January 2010 |

Volume: | Vol.17 |

Number: | No.1:R21 |

Status: | Peer Reviewed |

Access rights to Published version: | Open Access |

Funder: | Engineering and Physical Sciences Research Council (EPSRC) |

Grant number: | EP/D063191/1 (EPSRC) |

References: | [1] N. Alon and B. Sudakov, H-free graphs of large minimum degree, Elec. J. Combin. |

URI: | http://wrap.warwick.ac.uk/id/eprint/3285 |

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

### Actions (login required)

View Item |

### Downloads

Downloads per month over past year