Coloring a graph with $\Delta -1$ colors: Conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker

Daniel W. Cranston, Landon Rabern

Borodin and Kostochka conjectured that every graph $G$ with maximum degree $\Delta \ge 9$ satisfies $\chi \le \max \{\omega ,\Delta -1\}$. We carry out an in-depth study of minimum counterexamples to th…