On the List Coloring Version of Reed's Conjecture

It is natural to wonder if similar results hold for the list chromatic number. Unfortunately, previous techniques for ordinary coloring do not extend to list coloring. In this paper, we overcome these hurdles by introducing several new ideas. Our main result is that the list chromatic number is at most some non-trivial convex combination of the clique number and the maximum degree plus one. Furthermore, we show that for large enough maximum degree, that a combination of 1/13 suffices. Note that this also improves on the best known results for ordinary coloring.