A Lower Bound for Partial List Colorings

Abstract

Let G be an n-vertex graph with list-chromatic number ${\chi }_{\ell }$. Suppose each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas conjecture that at least $tn/{\chi }_{\ell }$ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a corollary, we show that at least 6/7 of the conjectured number can be colored.

4 pages, no figures