We prove a conjecture of András Gyárfás, that for all κ,ℓ, every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least ℓ.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics