Coloring a graph with Δ−1Δ−1 colors: Conjectures equivalent to the Borodin–Kostochka conjecture that appear weaker

Borodin and Kostochka conjectured that every graph GG with maximum degree Δ≥9Δ≥9 satisfies χ≤max{ω,Δ−1}χ≤max{ω,Δ−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 ff-choosable, where f(v)≔d(v)−1f(v)≔d(v)−1 for each vertex vv. Such a join cannot be an induced subgraph of a vertex critical graph with χ=Δχ=Δ, so 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 χ=Δ=9χ=Δ=9 contains K3∨K6¯ as a subgraph.