Ilkyoo Choi (최일규), The list version of the Borodin-Kostochka Conjecture for graphs with large maximum degree

Brooks’ Theorem states that for a graph G with maximum degree Δ(G) at least 3, the chromatic number is at most Δ(G) when the clique number is at most Δ(G). Vizing proved that the list chromatic number is also at most Δ(G) under the same conditions. Borodin and Kostochka conjectured that a graph G with maximum degree at least 9 must be (Δ(G)-1)-colorable when the clique number is at most Δ(G)-1; this was proven for graphs with maximum degree at least 10¹⁴ by Reed. We prove an analogous result for the list chromatic number; namely, we prove that a graph G with Δ(G)≥ 10²⁰ is (Δ(G)-1)-choosable when the clique number is at most Δ(G)-1. This is joint work with H. A. Kierstead, L. Rabern, and B. Reed.