En teoría de grafos , una rama de las matemáticas , la coloración de listas es un tipo de coloración de grafos en el que cada vértice puede restringirse a una lista de colores permitidos. Se estudió por primera vez en la década de 1970 en artículos independientes de Vizing y de Erdős , Rubin y Taylor. [1]
Dado un grafo G y dado un conjunto L ( v ) de colores para cada vértice v (llamado una lista ), una coloración de lista es una función de elección que asigna cada vértice v a un color en la lista L ( v ). Al igual que con la coloración de grafos, generalmente se supone que una coloración de lista es apropiada , lo que significa que no hay dos vértices adyacentes que reciban el mismo color. Un grafo es k -elegible (o k -coloreable por lista ) si tiene una coloración de lista apropiada sin importar cómo se asigne una lista de k colores a cada vértice. La capacidad de elección (o capacidad de coloración de lista o número cromático de lista ) ch( G ) de un grafo G es el menor número k tal que G es k -elegible.
En términos más generales, para una función f que asigna un entero positivo f ( v ) a cada vértice v , un grafo G es f -elegible (o f -coloreable por lista) si tiene una coloración de lista sin importar cómo se asigne una lista de f ( v ) colores a cada vértice v . En particular, si para todos los vértices v , la f -elegibilidad corresponde a k -elegibilidad.
Considérese el grafo bipartito completo G = K 2,4 , que tiene seis vértices A , B , W , X , Y , Z tales que A y B están cada uno conectado a todos los de W , X , Y y Z , y ningún otro vértice está conectado. Como grafo bipartito, G tiene número cromático usual 2: uno puede colorear A y B en un color y W , X , Y , Z en otro y ningún par de vértices adyacentes tendrán el mismo color. Por otro lado, G tiene número cromático de lista mayor que 2, como lo muestra la siguiente construcción: asigne a A y B las listas {rojo, azul} y {verde, negro}. Asigne a los otros cuatro vértices las listas {rojo, verde}, {rojo, negro}, {azul, verde} y {azul, negro}. No importa qué opción se elija de un color de la lista de A y de un color de la lista de B , siempre habrá algún otro vértice tal que ambas opciones ya se hayan utilizado para colorear a sus vecinos. Por lo tanto, G no es 2-elegible.
Por otra parte, es fácil ver que G es 3-elegible: elegir colores arbitrarios para los vértices A y B deja al menos un color disponible para cada uno de los vértices restantes, y estos colores pueden elegirse arbitrariamente.
De manera más general, sea q un entero positivo y sea G el grafo bipartito completo K q , q q . Sean los colores disponibles representados por los q 2 números diferentes de dos dígitos en base q . En un lado de la bipartición, sean los q vértices conjuntos de colores { i 0, i 1, i 2, ... } en los que los primeros dígitos sean iguales entre sí, para cada una de las q posibles elecciones del primer dígito i . En el otro lado de la bipartición, sean los q q vértices conjuntos de colores { 0 a , 1 b , 2 c , ... } en los que los primeros dígitos sean todos distintos, para cada una de las q q posibles elecciones de la q -tupla ( a , b , c , ...). La ilustración muestra un ejemplo más grande de la misma construcción, con q = 3.
Entonces, G no tiene una lista de colores para L : no importa qué conjunto de colores se elija para los vértices en el lado pequeño de la bipartición, esta elección entrará en conflicto con todos los colores para uno de los vértices en el otro lado de la bipartición. Por ejemplo, si el vértice con el conjunto de colores {00,01} está coloreado 01, y el vértice con el conjunto de colores {10,11} está coloreado 10, entonces el vértice con el conjunto de colores {01,10} no puede ser coloreado. Por lo tanto, el número cromático de lista de G es al menos q + 1. [2]
De manera similar, si , entonces el grafo bipartito completo K n , n no es k -elegible. Porque, supongamos que 2 k − 1 colores están disponibles en total, y que, en un solo lado de la bipartición, cada vértice tiene disponible una k -tupla diferente de estos colores que cada otro vértice. Entonces, cada lado de la bipartición debe usar al menos k colores, porque cada conjunto de k − 1 colores será disjunto de la lista de un vértice. Dado que al menos k colores se usan en un lado y al menos k se usan en el otro, debe haber un color que se use en ambos lados, pero esto implica que dos vértices adyacentes tienen el mismo color. En particular, el grafo de utilidad K 3,3 tiene número cromático de lista al menos tres, y el grafo K 10,10 tiene número cromático de lista al menos cuatro. [3]
Para un grafo G , sea χ( G ) el número cromático y Δ( G ) el grado máximo de G . El número de coloración de lista ch( G ) satisface las siguientes propiedades.
En la literatura se han considerado dos problemas algorítmicos:
Se sabe que la k -elegibilidad en grafos bipartitos es -completa para cualquier k ≥ 3, y lo mismo se aplica para la 4-elegibilidad en grafos planares, la 3-elegibilidad en grafos planares libres de triángulos y la (2, 3)-elegibilidad en grafos planares bipartitos . [9] [10] Para los grafos P 5 -libres, es decir, grafos que excluyen un grafo de trayectoria de 5 vértices , la k -elegibilidad es manejable con parámetros fijos . [11]
Es posible comprobar si un grafo es 2-elegible en tiempo lineal eliminando repetidamente vértices de grado cero o uno hasta alcanzar el 2-núcleo del grafo, después de lo cual ya no es posible realizar más eliminaciones de este tipo. El grafo inicial es 2-elegible si y solo si su 2-núcleo es un ciclo par o un grafo theta formado por tres caminos con puntos finales compartidos, con dos caminos de longitud dos y el tercer camino con cualquier longitud par. [3]
La coloración de listas surge en problemas prácticos relacionados con la asignación de canales/frecuencias. [12] [13]
Lectura adicional
