Coloring graphs from lists with bounded size of their union
Daniel Král͏̌, Jiřı́ Sgall · Journal of Graph Theory · 2005
Abstract A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,ℓ)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with $|\bigcup_{{ u}\in V(G)}\, L( u)|\le \ell$ . For each 3 ≤ k ≤ ℓ, we construct a graph G that is (k,ℓ)‐choosable but not (k,ℓ + 1)‐choosable. On the other hand, it is proven that each (k,2k − 1)‐choosable graph G is O(k · ln k · 24k)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory