Computer Science/Discrete Mathematics Seminar I

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