List Coloring with a Bounded Palette
Marthe Bonamy, Ross J. Kang · Journal of Graph Theory · 2015
Král' and Sgall (J Graph Theory 49(3) (2005), 177–186) introduced a refinement of list coloring where every color list must be subset to one predetermined palette of colors. We call this -choosability when the palette is of size at most ℓ and the lists must be of size at least k. They showed that, for any integer , there is an integer , satisfying as , such that, if a graph is -choosable, then it is C-choosable, and asked if C is required to be exponential in k. We demonstrate it must satisfy . For an integer , if is the least integer such that a graph is -choosable if it is -choosable, then we more generally supply a lower bound on , one that is super-polynomial in k if , by relation to an extremal set theoretic property. By the use of containers, we also give upper bounds on that improve on earlier bounds if .