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

Article English OPEN
Allen, Peter (2010)
  • Publisher: Electronic Journal of Combinatorics
  • Subject: QA

By using the Szemeredi Regularity Lemma, Alon and Sudakov recently\ud extended the classical Andrasfai-Erdos-Sos theorem to cover general graphs. We\ud prove, without using the Regularity Lemma, that the following stronger statement\ud is true.\ud Given any (r+1)-partite graph H whose smallest part has t vertices, there exists\ud a constant C such that for any given ε>0 and sufficiently large n the following is\ud true. Whenever G is an n-vertex graph with minimum degree\ud δ(G)≥(1 −\ud 3/3r−1 + ε)n,\ud either G contains H, or we can delete f(n,H)≤Cn2−1/t edges from G to obtain an\ud r-partite graph. Further, we are able to determine the correct order of magnitude\ud of f(n,H) in terms of the Zarankiewicz extremal function.
  • References (12)
    12 references, page 1 of 2

    [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, U¨ber 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.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Warwick Research Archives Portal Repository - IRUS-UK 0 56
Share - Bookmark