The ACO Seminar (2022–2023)

The classical theorem of Brooks tells us that if a graph $G$ has no colouring with its maximum degree $\Delta\geq 3$ colours, then it contains a clique with $\Delta+1$ vertices. Here we consider the analogous question when the number of colours is smaller than $\Delta$. Even the case of $\Delta-1$ colours is unknown: the famous Borodin-Kostochka Conjecture (1977) posits that if $\Delta\geq 9$ and $G$ has no $(\Delta-1)$-colouring then it contains a $\Delta(G)$-clique. Here we prove that for every nonnegative integer $t$ and every graph $G$ with maximum degree $\Delta(G)$ large enough with respect to $t$, if $G$ has chromatic number $\Delta(G)-t$ then it contains a clique with $\Delta(G)-2t^2-6t-3$ vertices. This generalizes (and provides an alternate proof for) a theorem of Cranston and Rabern, and of Mozhan, who proved the statement for the case $t=0$. Their result is the best known approximation to the Borodin-Kostochka Conjecture. Our result can also be viewed as a weak form of a statement conjectured by Reed, that quantifies more generally how large a clique a graph should contain if its chromatic number is close to its maximum degree. This is joint work with Colter MacDonald.