The list chromatic number of graphs with small clique number

Abstract

We prove that every triangle-free graph with maximum degree $\Delta$ has list chromatic number at most $(1+o(1))\frac{\Delta }{\ln \Delta }$. This matches the best-known bound for graphs of girth at least 5. We also provide a new proof that for any $r\ge 4$ every $K_r$-free graph has list-chromatic number at most $200r\frac{\Delta \ln \ln \Delta }{\ln \Delta }$.

arXiv commentRevised according to referee reports