14:30
A "hole" in a graph is an induced subgraph which is a cycle of length > 3. The perfect graph theorem says that if a graph has no odd holes and no odd antiholes (the complement of a hole), then its chromatic number equals its clique number; but unrestricted graphs can have clique number two and arbitrarily large chromatic number. There is a nice question half-way between them - for which classes of graphs is it true that a bound on clique number implies some (larger) bound on chromatic number? Call this being "chi-bounded".
Gyarfas proposed several conjectures of this form in 1985, and recently there has been significant progress on them. For instance, he conjectured
- graphs with no odd hole are chi-bounded (this is true);
- graphs with no hole of length >100 are chi-bounded (this is true);
- graphs with no odd hole of length >100 are chi-bounded; this is still open but true for triangle-free graphs.
We survey this and several related results. This is joint with Alex Scott and partly with Maria Chudnovsky.