Induced subgraphs of graphs with large chromatic number. I. Odd holes
Alex Scott, Paul D. Seymour · arXiv (Cornell University) · 2014
An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyarfas made the conjecture that for all t there exists n such that every graph with no K_t subgraph and no odd hole is n-colourable. We prove this conjecture.