<p>As a bit of unashamed self-promotion, Marthe Bonamy and I found more negative answers. In particular, Theorem 4 of <a href="http://arxiv.org/abs/1507.03495" rel="nofollow">http://arxiv.org/abs/1507.03495</a> 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.</p>

<p>The work was motivated in part by this TCS overflow question.</p>

CC BY-SA 3.0
2015-08-10T14:37:27.740Z
2015-08-10T22:58:15.737Z
2015-08-10T22:58:15.737Z
RJK
<p>Daniel Král and Jiří Sgall answered your question to the negative. From the abstract of their paper:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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$.</p>

<p>Daniel Král, Jiří Sgall: <a href="http://dx.doi.org/10.1002/jgt.20073">Coloring graphs from lists with bounded size of their union</a>. Journal of Graph Theory 49(3): 177-186 (2005)</p>

CC BY-SA 2.5
2011-02-11T13:27:09.453Z
Wow. This settles the question, although negatively. Thank you @Serge! And I wish I could give thanks to Daniel and Jiří too!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-11T14:34:16.107Z
I would also have preferred a positive answer to the question.
Serge Gaspers
CC BY-SA 2.5
2011-02-11T12:45:28.040Z
2011-02-11T12:45:28.040Z
Serge Gaspers
<p>A graph is $k$-choosable (also known as <a href="http://en.wikipedia.org/wiki/List_coloring">$k$-list-colorable</a>) 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)$.</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-19T18:08:52.673Z
My first thought is to try to lower bound the number of colors required in the standard example that bipartite graphs can have arbitrarily-high list-chromatic number.  However, the number of colors in the list in this construction is exponential to the achieved $k$.  I didn't take enough time to prove the lower bound, however (so this isn't an answer...yet).
Derrick Stolee
CC BY-SA 2.5
2011-02-06T13:09:07.560Z
It might be worth posting this excellent question on MathOverflow too...
François G. Dorais
CC BY-SA 2.5
2011-02-08T19:05:42.860Z
Does setting $k=1$ in Corollary 1.4 [here](http://arxiv.org/PS_cache/arxiv/pdf/0802/0802.2157v1.pdf) answer at least part of your question?
Aaron Sterling
CC BY-SA 2.5
2011-02-08T22:41:19.920Z
@Aaron: I'm not sure what you mean. If I set k=1 in that corollary it seems to say that the choice number is at most the chromatic number times a log factor; but it doesn't seems to say much about how many distinct colors are needed for that choice number.
David Eppstein
CC BY-SA 2.5
2011-02-09T15:12:24.923Z
Yes, of course you're right, David, my apologies.  I've been a cstheory space cadet the last ten days or so, it seems.  (Maybe longer......)
Aaron Sterling
CC BY-SA 2.5
2011-02-09T23:03:43.977Z
I think I've asked this question to a few people and never really had a very interesting response.  I wonder if looking at the Alon-Tarsi orientation/nullstellensatz approach would give you any interesting bounds...
Andrew D. King
CC BY-SA 2.5
2010-11-04T22:35:00.080Z
Is there an example when N(k)>2k-1?
Yaroslav Bulatov
<graph-theory><co.combinatorics><graph-colouring><exp-time-algorithms>
How many distinct colors are needed to lower-bound the choosability of a graph?
David Eppstein
# How many distinct colors are needed to lower-bound the choosability of a graph?

(Asked by: username_0 on 2010-11-02)

A graph is $k$-choosable (also known as [$k$-list-colorable](http://en.wikipedia.org/wiki/List_coloring)) 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.

**Tags:** graph-theory, co.combinatorics, graph-colouring, exp-time-algorithms
> **Comments:**
> **username_5**: Is there an example when N(k)>2k-1?  
> **username_1**: My first thought is to try to lower bound the number of colors required in the standard example that bipartite graphs can have arbitrarily-high list-chromatic number.  However, the number of colors in the list in this construction is exponential to the achieved $k$.  I didn't take enough time to prove the lower bound, however (so this isn't an answer...yet).  
> **username_2**: It might be worth posting this excellent question on MathOverflow too...  
> **username_3**: Does setting $k=1$ in Corollary 1.4 [here](http://arxiv.org/PS_cache/arxiv/pdf/0802/0802.2157v1.pdf) answer at least part of your question?  
> **username_0**: @Aaron: I'm not sure what you mean. If I set k=1 in that corollary it seems to say that the choice number is at most the chromatic number times a log factor; but it doesn't seems to say much about how many distinct colors are needed for that choice number.  
> **username_3**: Yes, of course you're right, David, my apologies.  I've been a cstheory space cadet the last ten days or so, it seems.  (Maybe longer......)  
> **username_4**: I think I've asked this question to a few people and never really had a very interesting response.  I wonder if looking at the Alon-Tarsi orientation/nullstellensatz approach would give you any interesting bounds...  

---

## 2 answers

### Answer by username_7 on 2011-02-11. Score: 23 | Accepted answer

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](http://dx.doi.org/10.1002/jgt.20073). Journal of Graph Theory 49(3): 177-186 (2005)

> **Comments:**
> **username_8**: Wow. This settles the question, although negatively. Thank you @Serge! And I wish I could give thanks to Daniel and Jiří too!  
> **username_7**: I would also have preferred a positive answer to the question.  

---

### Answer by username_6 on 2015-08-10. Score: 8

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.


---

