Ile różnych kolorów jest potrzebnych, aby ograniczyć możliwości wyboru wykresu?

Wykres jest $k$ wyboru (znany również jako $k$ -list-colorable ), jeśli dla każdej funkcji $f$ która odwzorowuje wierzchołki na zestawy $k$ kolorów, istnieje przypisanie kolorów $c$ tak że dla wszystkich wierzchołków $v$ , $c(v)\in f(v)$ i takie, że dla wszystkich krawędzi $vw$ , $c(v)\ne c(w)$ .

Załóżmy teraz, że wykres $G$ nie jest $k$ -choosable. Oznacza to, że istnieje funkcja $f$ od wierzchołków do $k$ -kolorów kolorów, która nie ma prawidłowego przypisania kolorów $c$ . Chcę wiedzieć, ile łącznie kolorów jest potrzebnych? Jak mały może być $\cup_{v\in G}f(v)$ ? Czy istnieje liczba $N(k)$ (niezależna od $G$ ) taka, że ​​możemy zagwarantować, że znajdziemy bezbarwną $f$ która używa tylko $N(k)$ różnych kolorów?

Istotność dla CS polega na tym, że jeśli $N(k)$ istnieje, możemy przetestować $k$ echosowalność dla stałej $k$ w czasie pojedynczo wykładniczym (po prostu wypróbuj wszystkie wyborów , i dla każdego sprawdź, czy można go pokolorować w czasie ), podczas gdy w przeciwnym razie może być wymagane coś szybszego, np. .$\binom{N(k)}{k}^n$$f$$k^n n^{O(1)}$$n^{kn}$

Daniel Král i Jiří Sgall odpowiedzieli na Twoje pytanie przecząco. Z streszczenia ich pracy:

O wykresie mówi się, że można zamieniać, jeśli jego wierzchołki można pokolorować z dowolnej listy pomocą , dla wszystkich , i za pomocą . Dla każdego konstruujemy wykres który jest -kosowalny, ale nie -kosowalny.$G$$(k,\ell)$$L(v)$$|L(v)| \ge k$$v\in V(G)$$|\bigcup_{v\in V(G)} L(v)| \le \ell$$3 \le k \le \ell$$G$$(k,\ell)$$(k,\ell+1)$

Zatem nie istnieje, jeśli . Král i Sgall pokazują również, że . Oczywiście .$N(k)$$k\ge 3$$N(2)=4$$N(1)=1$

Daniel Král, Jiří Sgall: Kolorowanie wykresów z list o ograniczonym rozmiarze ich związku . Journal of Graph Theory 49 (3): 177-186 (2005)

Jako trochę bezwstydnej autopromocji, Marthe Bonamy i ja znaleźliśmy więcej negatywnych odpowiedzi. W szczególności Twierdzenie 4 z http://arxiv.org/abs/1507.03495 poprawia wyżej wspomniany wynik Krála i Sgalla w niektórych przypadkach. Przykłady, których używamy, to kompletne wykresy dwudzielne, w których do analizy wykorzystaliśmy ekstremalne kombinatoryki.

Praca była częściowo motywowana pytaniem dotyczącym przelewu TCS.