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

Abstract

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 the Borodin-Kostochka conjecture. Our main tool is the identification of graph joins that are $f$-choosable, where $f(v)=d(v)-1$ for each vertex $v$. Since such a join cannot be an induced subgraph of a vertex critical graph with $\chi =\Delta$, we have a wealth of structural information about minimum counterexamples to the Borodin-Kostochka conjecture. Our main result proves that certain conjectures that are prima facie weaker than the Borodin-Kostochka conjecture are in fact equivalent to it. One such equivalent conjecture is the following: Any graph with $\chi \ge \Delta =9$ contains $K_3\ast \overline{K_6}$ as a subgraph.

arXiv commentcompact version only proving the list coloring results needed for the conjecture equivalences; 26 pages, 6 figures; final version accepted for publication