Colouring graphs without odd holes

-
Alex Scott, Oxford University
Fine Hall 224

Gyarfas conjectured in 1985 that if G is a graph with no induced cycle of odd length at least 5, then the chromatic number of G is bounded by a function of its clique number. We present a proof of this conjecture, in joint work with Paul Seymour. We also discuss some further results, with Maria Chudnovsky and Paul Seymour.