39

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.

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • 1
    Is there an example when N(k)>2k-1? – Yaroslav Bulatov Nov 04 '10 at 22:35
  • 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). – Derrick Stolee Dec 19 '10 at 18:08
  • 1
    It might be worth posting this excellent question on MathOverflow too... – François G. Dorais Feb 06 '11 at 13:09
  • Does setting $k=1$ in Corollary 1.4 here answer at least part of your question? – Aaron Sterling Feb 08 '11 at 19:05
  • @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 Feb 08 '11 at 22:41
  • 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 Feb 09 '11 at 15:12
  • 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 Feb 09 '11 at 23:03

2 Answers2

23

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)

Serge Gaspers
  • 5,116
  • 29
  • 42
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.

RJK
  • 1,952
  • 1
  • 19
  • 27