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

Abstract

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 $\Delta \ge 13$ and $\omega \le \Delta -4$, then $\chi \le \Delta -1$. For a graph $G$, let $\mathcal{H}$ denote the subgraph of $G$ induced by vertices of degree $\Delta$. We also show that if $\omega \le \Delta -1$ and $\omega (\mathcal{H})\le \Delta -6$, then $\chi \le \Delta -1$.

27 pages, 3 figures; added many more details in this version, as well as a discussion of algorithms; to appear in SIAM J. Discrete Math