¿Cuántos colores distintos se necesitan para limitar la posibilidad de elegir un gráfico?

39

Un gráfico es k elegible (también conocido como k -list-colorable ) si, para cada función F que asigna vértices a conjuntos de k colores, hay una asignación de color do tal que, para todos los vértices v , c(v)f(v) , y tal que, para todos los bordes vw , c(v)c(w) .

Ahora suponga que una gráfica sol no es k elegible. Es decir, existe una función F desde vértices hasta k -tuplas de colores que no tiene una asignación de color válida do . Lo que quiero saber es, ¿qué pocos colores en total se necesitan? ¿Qué tan pequeño puede ser vGf(v) ? ¿Hay un número N(k) (independiente de sol ) tal que podamos garantizar que encontremos una incolora Fque solo usa N(k) colores distintos?

La relevancia para CS es que, si existe, podemos probar capacidad de elección para constante en tiempo exponencial simple (solo intente todas las opciones de , y para cada uno, verifique que se pueda colorear a tiempo ) mientras que de lo contrario podría requerirse algo que crezca más rápidamente como .norte(k)k ( N ( k )kkfknnO(1)nkn(norte(k)k)norteFknortenorteO(1)nkn

David Eppstein
fuente
1
¿Hay algún ejemplo cuando N (k)> 2k-1?
Yaroslav Bulatov el
1
Mi primer pensamiento es intentar reducir el número de colores requeridos en el ejemplo estándar de que los gráficos bipartitos pueden tener un número cromático de lista arbitrariamente alto. Sin embargo, el número de colores en la lista en esta construcción es exponencial al alcanzado . Sin embargo, no me tomé el tiempo suficiente para probar el límite inferior (por lo que esta no es una respuesta ... todavía). k
Derrick Stolee
1
También podría valer la pena publicar esta excelente pregunta en MathOverflow ...
François G. Dorais
¿Establecer en el Corolario 1.4 aquí responde al menos parte de su pregunta? k=1
Aaron Sterling
@ Aaron: No estoy seguro de lo que quieres decir. Si establezco k = 1 en ese corolario, parece decir que el número de elección es como máximo el número cromático multiplicado por un factor logarítmico; pero no parece decir mucho sobre cuántos colores distintos se necesitan para ese número de elección.
David Eppstein

Respuestas:

21

Daniel Král y Jiří Sgall respondieron negativamente a su pregunta. Del resumen de su artículo:

Un gráfico se dice que es ( k , ) -choosable si sus vértices se pueden colorear de cualquier listas L ( v ) con | L ( v ) | k , para todos v V ( G ) , y con | v V ( G ) L ( v ) | . Por cada 3 k G(k,)L(v)|L(v)|kvV(G)|vV(G)L(v)|3k, construimos un gráfico que es elegible ( k , ) pero no elegible ( k , + 1 ) .G(k,)(k,+1)

Entonces, no existe si k 3 . Král y Sgall también muestran que N ( 2 ) = 4 . Por supuesto, N ( 1 ) = 1 .N(k)k3N(2)=4N(1)=1

Daniel Král, Jiří Sgall: Colorear gráficos de listas con el tamaño acotado de su unión . Journal of Graph Theory 49 (3): 177-186 (2005)

Serge Gaspers
fuente
Guau. Esto resuelve la pregunta, aunque negativamente. Gracias @Serge! ¡Y desearía poder agradecer a Daniel y Jiří también!
Hsien-Chih Chang 張顯 之
También hubiera preferido una respuesta positiva a la pregunta.
Serge Gaspers
8

Como un poco de auto-promoción descarada, Marthe Bonamy y yo encontramos más respuestas negativas. En particular, el Teorema 4 de http://arxiv.org/abs/1507.03495 mejora el resultado antes mencionado de Král 'y Sgall en ciertos casos. Los ejemplos que utilizamos son gráficos bipartitos completos, donde utilizamos algunos combinatorios extremos para analizarlos.

El trabajo fue motivado en parte por esta pregunta de desbordamiento de TCS.

RJK
fuente