ACO The ACO Seminar (2022–2023)

December 8, 3:30pm, Wean 8220
Penny Haxell, University of Waterloo
Large Cliques in Graphs with High Chromatic Number


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.

Back to the ACO home page Back to the ACO Seminar schedule