# Colouring graphs with no odd holes

 Computer Science/Discrete Mathematics Seminar I Topic: Colouring graphs with no odd holes Speaker: Paul Seymour Affiliation: Princeton University Date: Monday, September 22 Time/Room: 11:15am - 12:15pm/S-101 Video Link: http://video.ias.edu/csdm/2014/0922-PaulSeymour

The chromatic number $k(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $w(G)$), and there are graphs with $w(G)=2$ and $k(G)$ arbitrarily large. On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $k(G)=w(G)$. (An odd hole" is an induced cycle of odd length at least five.) What happens in between? With Alex Scott, we have just proved the following, a 1985 conjecture of Gyarfas: For graphs $G$ with no odd hole, $k(G)$ is bounded by a function of $w(G)$.