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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics