Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 1-9 |
Number of pages | 9 |
Journal | Electronic Journal of Combinatorics |
Volume | 13 |
Issue number | 1 R |
DOIs | |
State | Published - Mar 7 2006 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics