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

39

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 )kkfkcvc(v)f(v)vwc(v)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 )GkfkcvGf(v)N(k)GfN(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)kkfknnO(1)nkn(N(k)k)nfknnO(1)nkn

David Eppstein
fonte
1
Existe um exemplo quando N (k)> 2k-1?
Yaroslav Bulatov
1
Meu primeiro pensamento é tentar limitar o número de cores necessário no exemplo padrão de que os gráficos bipartidos podem ter um número cromático de lista arbitrariamente alto. No entanto, o número de cores na lista nesta construção é exponencial ao obtido . No entanto, não demorei bastante para provar o limite inferior (portanto, essa não é uma resposta ... ainda). k
Derrick Stolee,
1
Pode valer a pena postar esta excelente pergunta sobre MathOverflow também ...
François G. Dorais
A definição de no Corolário 1.4 aqui responde a pelo menos parte de sua pergunta? k=1
Aaron Sterling
@ Aaron: Não sei o que você quer dizer. Se eu definir k = 1 nesse corolário, parece dizer que o número de escolha é no máximo o número cromático vezes um fator logarítmico; mas não parece dizer muito sobre quantas cores distintas são necessárias para esse número de escolha.
David Eppstein

Respostas:

21

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,)L(v)|L(v)|kvV(G)|vV(G)L(v)|3k, construímos um gráfico que é ( k , ) selecionável, mas não ( k , + 1 ) selecionável.G(k,)(k,+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)k3N(2)=4N(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)

Serge Gaspers
fonte
Uau. Isso resolve a questão, embora negativamente. Obrigado @Serge! E gostaria de poder agradecer também a Daniel e Jiří!
Hsien-Chih Chang #: 11/02/11
Eu também teria preferido uma resposta positiva para a pergunta.
Serge Gaspers
8

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.

RJK
fonte