Colouring graphs with no odd holes

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

Date

Speakers

Paul Seymour

Affiliation

Princeton University

Files & Media