List-Coloring Claw-Free Graphs with $\Delta-1$ Colors
Daniel W. Cranston, Landon Rabern · SIAM Journal on Discrete Mathematics · 2017
Let $\chi_{\ell}$ and $\chi_{OL}$ denote the list-chromatic number and online list-chromatic number. We prove that if $G$ is a quasi-line graph with maximum degree greater than clique number, i.e., $\Delta(G)>\omega(G)$, and $\Delta(G)\ge 69$, then its online list-chromatic number is less than its maximum degree, i.e., $\chi_{OL}(G)\le \Delta(G)-1$. Together with our previous work, this implies that if $G$ is a claw-free graph with $\Delta(G)>\omega(G)$ and $\Delta(G)\ge 69$, then its list-chromatic number is less than its maximum degree, i.e., $\chi_{\ell}(G)\le \Delta(G)-1$. This verifies the list-coloring analogue of a conjecture of Borodin and Kostochka for every claw-free graph $G$ with $\Delta(G)\ge 69$.