The list version of the Borodin-Kostochka Conjecture for graphs with large maximum degree

Ilkyoo Choi (최일규)

Department of Mathematics, University of Illinois at Urbana-Champaign, IL, USA

Department of Mathematics, University of Illinois at Urbana-Champaign, IL, USA

2012/12/27

*Thu*4PM-5PMBrooks’ 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

^{14}by Reed. We prove an analogous result for the list chromatic number; namely, we prove that a graph G with Δ(G)≥ 10^{20}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.