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