List Coloring with a Bounded Palette |
| |
| Authors: | Marthe Bonamy Ross J. Kang |
| |
| Affiliation: | 1. UNIVERSITé MONTPELLIER 2 – LIRMM, MONTPELLIER, FRANCEThis research was carried out during a visit by this author to Utrecht University. Contract grant sponsor: ANR Grant EGOS (2012–2015) 12 JS02 002 01 (to M. B.);2. Contract grant sponsor: NWO Veni grant (project number 639.031.138) (to R. J. K.).;3. APPLIED STOCHASTICS, RADBOUD UNIVERSITY NIJMEGEN, NIJMEGEN, NETHERLANDS |
| |
| Abstract: | 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  . |
| |
| Keywords: | graph coloring list coloring probabilistic method |
|
|
