39
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Is there an example when N(k)>2k-1? $\endgroup$ – Yaroslav Bulatov Nov 4 '10 at 22:35
  • 1
    $\begingroup$ 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). $\endgroup$ – Derrick Stolee Dec 19 '10 at 18:08
  • 1
    $\begingroup$ It might be worth posting this excellent question on MathOverflow too... $\endgroup$ – François G. Dorais Feb 6 '11 at 13:09
  • $\begingroup$ Does setting $k=1$ in Corollary 1.4 here answer at least part of your question? $\endgroup$ – Aaron Sterling Feb 8 '11 at 19:05
  • $\begingroup$ @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. $\endgroup$ – David Eppstein Feb 8 '11 at 22:41
21
+100
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Wow. This settles the question, although negatively. Thank you @Serge! And I wish I could give thanks to Daniel and Jiří too! $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 11 '11 at 13:27
  • $\begingroup$ I would also have preferred a positive answer to the question. $\endgroup$ – Serge Gaspers Feb 11 '11 at 14:34
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.