Сколько разных цветов необходимо для того, чтобы ограничить возможность выбора графика?

Граф является выбираемым (также известным как -list-colourable ), если для каждой функции которая отображает вершины в наборы из цветов, существует такое цветовое присвоение , что для всех вершин , , и такие , что для всех ребер Vw , с (v) \ п с (ш) .k f k c v c ( v ) ∈ f ( v ) v w c ( v ) ≠ c ( w $k$$k$$f$$k$$c$$v$$c(v)\in f(v)$$vw$$c(v)\ne c(w)$

Теперь предположим, что граф не является выбираемым. Таким образом, существует функция из вершин в наборов цветов, которая не имеет правильного назначения цветов . Я хочу знать, сколько всего цветов нужно? Насколько маленьким может быть ? Существует ли число (не зависящее от ) такое, что мы можем гарантировать, что найдем неокрашиваемое которое использует только разных цветов?k f k c ∪ v ∈ G f ( v ) N ( k ) G f N ( k $G$$k$$f$$k$$c$$\cup_{v\in G}f(v)$$N(k)$$G$$f$$N(k)$

Актуальность для CS заключается в том, что, если существует, мы можем проверить выбираемость для константы за единичное экспоненциальное время (просто попробуйте все вариантов , и для каждой проверки, что он может быть окрашен во времени ), тогда как в противном случае может потребоваться что-то более быстрое, например .k $N(k)$$k$$k$nk$\binom{N(k)}{k}^n$k n n O ( 1 $f$$k^n n^{O(1)}$$n^{kn}$

Даниэль Крал и Йиржи Сгалл ответили на ваш вопрос отрицательно. Из аннотации их статьи:

Граф называется -выбираемым, если его вершины можно раскрасить из любых списков с помощью , для всех и с . Для каждого строится граф который -выбираем, но не -выбираем.( k , ℓ ) L ( v ) | L ( v ) | ≥ k v ∈ V ( G ) | ⋃ v ∈ V ( G ) L ( v ) | ≤ ℓ 3 ≤ k ≤ ℓ G ( k , ℓ ) ( k , ℓ + 1 $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)$

Итак, не существует, если . Крал и Сгалл также показывают, что . Конечно, .k ≥ 3 N ( 2 ) = 4 N ( 1 ) = $N(k)$$k\ge 3$$N(2)=4$$N(1)=1$

Даниэль Крал, Йиржи Сгалл: раскраска графиков из списков с ограниченным размером их объединения . Журнал теории графов 49 (3): 177-186 (2005)

В качестве самостоятельной саморекламы мы с Мартой Бонами нашли больше отрицательных ответов. В частности, теорема 4 http://arxiv.org/abs/1507.03495 улучшает вышеупомянутый результат Краля и Сгалла в некоторых случаях. Примерами, которые мы используем, являются полные двудольные графы, где мы использовали некоторую экстремальную комбинаторику для их анализа.

Работа была мотивирована частично этим вопросом переполнения TCS.