How many distinct colors are needed to lower-bound the choosability of a graph?

Question

A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, $c(v)\in f(v)$, and such that, for all edges $vw$, $c(v)\ne c(w)$.

Now suppose that a graph $G$ is not $k$-choosable. That is, there exists a function $f$ from vertices to $k$-tuples of colors that does not have a valid color assignment $c$. What I want to know is, how few colors in total are needed? How small can $\cup_{v\in G}f(v)$ be? Is there a number $N(k)$ (independent of $G$) such that we can be guaranteed to find an uncolorable $f$ that only uses $N(k)$ distinct colors?

The relevance to CS is that, if $N(k)$ exists, we can test $k$-choosability for constant $k$ in singly-exponential time (just try all $\binom{N(k)}{k}^n$ choices of $f$, and for each one check that it can be colored in time $k^n n^{O(1)}$) whereas otherwise something more quickly growing like $n^{kn}$ might be required.

Answer 1

Daniel Král and Jiří Sgall answered your question to the negative. From the abstract of their paper:

A graph $G$ is said to be $(k,\ell)$-choosable if its vertices can be colored from any lists $L(v)$ with $|L(v)| \ge k$, for all $v\in V(G)$, and with $|\bigcup_{v\in V(G)} L(v)| \le \ell$. For each $3 \le k \le \ell$, we construct a graph $G$ that is $(k,\ell)$-choosable but not $(k,\ell+1)$-choosable.

So, $N(k)$ does not exist if $k\ge 3$. Král and Sgall also show that $N(2)=4$. Of course, $N(1)=1$.

Daniel Král, Jiří Sgall: Coloring graphs from lists with bounded size of their union. Journal of Graph Theory 49(3): 177-186 (2005)

Answer 2

As a bit of unashamed self-promotion, Marthe Bonamy and I found more negative answers. In particular, Theorem 4 of http://arxiv.org/abs/1507.03495 improves upon the aforementioned result of Král' and Sgall in certain cases. The examples we use are complete bipartite graphs, where we used some extremal combinatorics to analyse them.

The work was motivated in part by this TCS overflow question.