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:

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)\).