H-free graphs of large minimum degree

Noga Alon, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We prove the following extension of an old result of Andrásfai, Erdos and Sós. For every fixed graph H with chromatic number r + 1 ≥ 3, and for every fixed ε > 0, there are no = no(H, ε) and ρ = ρ(H) > 0, such that the following holds. Let G be an H-free graph on n > n0 vertices with minimum degree at least (1 - 1/r-1/3 + ε) n. Then one can delete at most n2-ρ edges to make G r-colorable.

Original languageEnglish (US)
Pages (from-to)1-9
Number of pages9
JournalElectronic Journal of Combinatorics
Issue number1 R
StatePublished - Mar 7 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'H-free graphs of large minimum degree'. Together they form a unique fingerprint.

Cite this