# 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 |

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. 13 (2006), R19. [2] B. Andr´asfai, P. Erd˝os, and V. T. S´os, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218. [3] W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281–285. [4] P. Erd˝os, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183–190. [5] P. Erd˝os and M. Simonovits, On a valence problem in extremal graph theory, Discrete Math. 5 (1973), 323–334. [6] P. Erd˝os and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087–1091. [7] J. Koll´ar, L. R´onyai, and T. Szabo, Norm-graphs and bipartite Tur´an numbers, Combinatorica 16 (1996), 399–406. [8] T. K¨ov´ari, V. T. S´os, and P. Tur´an, On a problem of K. Zarankiewicz, Colloquium Math. 3 (1954), 50–57. [9] I. Reiman, ¨ Uber ein problem von K. Zarankiewicz, Acta. Math. Acad. Sci. Hungar. 9 (1958), 269–279. [10] E. Szemer´edi, Regular partitions of graphs, Probl`emes combinatoires et th´eorie des graphes (Orsay, 1976), Colloques Internationaux CNRS, vol. 260, CNRS, 1978, pp. 399–401. [11] P. Tur´an, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452. [12] K. Zarankiewicz, Sur les relations sym´etriques dans l’ensemble fini, Colloq. Math. 1 (1947), 10–14. |

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

Data sourced from Thomson Reuters' Web of Knowledge

### Actions (login required)

View Item |