Tutte Colloquium - Penny Haxell

Title: Graphs with High Chromatic Number

Abstract: The classical theorem of Brooks tells us that if a graph G has no colouring with its maximum degree ∆≥3 colours, then it contains a clique with ∆+1 vertices. Does a similar phenomenon occur when the chromatic number is slightly smaller than ∆? Even the next case is unknown: in 1977, Borodin and Kostochka famously conjectured that if ∆≥9 and G has no (∆-1)-colouring then it contains a ∆(G)-clique. We discuss various results and questions around this conjecture.