Quantas cores distintas são necessárias para limitar a escolha de um gráfico?

Um gráfico é choosable (também conhecido como -list-colorable ) se, para cada função que mapeia vértices para conjuntos de cores, há uma atribuição de cores tal que, para todos os vértices , , e tal que, para todas as arestas , .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)$

Agora, suponha que um gráfico não seja selecionável. Ou seja, existe uma função de vértices a pares de cores que não possui uma atribuição de cores válida . O que eu quero saber é: quantas cores são necessárias no total? Quão pequeno pode ser ? Existe um número (independente de ) de forma que possamos garantir um incolor que usa apenas cores distintas?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)$

A relevância para CS é que, se existe, podemos testar a capacidade de para constante em tempo exponencial único (apenas tente todas as opções de de , e para cada um, verifique se pode ser colorido com o tempo ), enquanto, caso contrário, algo que cresce mais rapidamente como pode ser necessário.k k ( N ( k $N(k)$$k$$k$fknnO(1)nk$\binom{N(k)}{k}^n$$f$$k^n n^{O(1)}$$n^{kn}$

Daniel Král e Jiří Sgall responderam à sua pergunta de forma negativa. Do resumo de seu trabalho:

Diz-se que um gráfico pode ser escolhido ( k , ℓ ) se seus vértices puderem ser coloridos de qualquer lista L ( v ) com | L ( v ) | ≥ k , para todos v ∈ V ( G ) e com | ⋃ v ∈ V ( L ) L ( v ) | ≤ ℓ . Para cada 3 ≤ k ≤ $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$, construímos um gráfico que é ( k , ℓ ) selecionável, mas não ( k , ℓ + 1 ) selecionável.$G$$(k,\ell)$$(k,\ell+1)$

Portanto, não existe se k ≥ 3 . Král e Sgall também mostram que N ( 2 ) = 4 . Obviamente, N ( 1 ) = 1 .$N(k)$$k\ge 3$$N(2)=4$$N(1)=1$

Daniel Král, Jiří Sgall: Colorir gráficos de listas com tamanho delimitado de sua união . Journal of Graph Theory 49 (3): 177-186 (2005)

Como um pouco de autopromoção sem vergonha, Marthe Bonamy e eu encontramos respostas mais negativas. Em particular, o Teorema 4 de http://arxiv.org/abs/1507.03495 melhora o resultado acima mencionado de Král 'e Sgall em certos casos. Os exemplos que usamos são gráficos bipartidos completos, nos quais usamos algumas combinações extremais para analisá-los.

O trabalho foi motivado em parte por essa questão do estouro do TCS.