Graphs with $\chi =\Delta$ have big cliques

Daniel W. Cranston, Landon Rabern

Brooks' Theorem states that if a graph has $\Delta \ge 3$ and $\omega \le \Delta$, then $\chi \le \Delta$. Borodin and Kostochka conjectured that if $\Delta \ge 9$ and $\omega \le \Delta -1$, then $\chi \le \Delta -1$. We show that if…