Un gráfico es elegible (también conocido como -list-colorable ) si, para cada función que asigna vértices a conjuntos de colores, hay una asignación de color tal que, para todos los vértices , , y tal que, para todos los bordes , .
Ahora suponga que una gráfica no es elegible. Es decir, existe una función desde vértices hasta -tuplas de colores que no tiene una asignación de color válida . Lo que quiero saber es, ¿qué pocos colores en total se necesitan? ¿Qué tan pequeño puede ser ? ¿Hay un número (independiente de ) tal que podamos garantizar que encontremos una incolora que solo usa 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 .k ( N ( k )fknnO(1)nkn
fuente
Respuestas:
Daniel Král y Jiří Sgall respondieron negativamente a su pregunta. Del resumen de su artículo:
Entonces, no existe si k ≥ 3 . Král y Sgall también muestran que N ( 2 ) = 4 . Por supuesto, N ( 1 ) = 1 .N(k) k≥3 N(2)=4 N(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)
fuente
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.
fuente