Coloring graphs from lists with bounded size of their union

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_{{\nu}\in V(G)}\, L(\nu)|\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 ,2 k  − 1)‐choosable graph G is O ( k  · ln k  · 2 4 k )‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory