The chromatic number of graphs without long holes

The chromatic number of graphs without long holes

-
Alex Scott, Oxford University
Fine Hall 224

Andras Gyarfas conjectured in 1985 that for all k and t, every graph with sufficiently large chromatic number contains either a complete subgraph on k vertices or an induced cycle of length at least t. We prove this conjecture and discuss some related results. Joint work with Maria Chudnovsky and Paul Seymour.