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