Borodin–Kostochka conjecture

All graphs considered are finite, simple, and undirected. For a graph $G$, let $\chi(G)$ denote its chromatic number, $\omega(G)$ its clique number, and $\Delta(G)$ its maximum degree. Borodin–Kostochka conjecture. If

$$\Delta(G)\geq 9\quad\text{and}\quad \omega(G)\leq \Delta(G)-1,$$

then

$$\chi(G)\leq \Delta(G)-1.$$

This conjecture asks for a strengthening of Brooks' theorem when the maximum degree is at least $9$ and the clique number is strictly smaller than the maximum degree. It remains open in the supplied source context; the paper studies the conjecture for $(P_6,C_4)$-free graphs.