En teoría de grafos , una rama de las matemáticas , la coloración de listas es un tipo de coloración de gráficos donde cada vértice se puede restringir a una lista de colores permitidos. Fue estudiado 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 gráfico G y un conjunto L ( v ) de colores para cada vértice v (llamado 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 gráficos, generalmente se supone que la coloración de una lista es adecuada , lo que significa que no hay dos vértices adyacentes que reciban el mismo color. Un gráfico es k -seleccionable (o k -list-colorable ) si tiene una lista de colores adecuada, sin importar cómo se asigne una lista de k colores a cada vértice. La capacidad de elección (o colorabilidad de la lista o número cromático de la lista ) ch ( G ) de un gráfico G es el menor número k tal que G sea k seleccionable.
De manera más general, para una función f que asigna un entero positivo f ( v ) a cada vértice v , un gráfico G es f -seleccionable (o f -list-colorable ) si tiene un color de lista sin importar cómo se asigne una lista de f ( v ) colores para cada vértice v . En particular, si para todos los vértices v , f -elección corresponde a k -elección.
Considere el gráfico bipartito completo G = K 2,4 , que tiene seis vértices A , B , W , X , Y , Z tales que A y B están conectados a todos W , X , Y y Z , y ningún otro vértice estan conectados. Como gráfico bipartito, G tiene el número cromático habitual 2: se pueden colorear A y B en un color y W , X , Y , Z en otro y no hay dos vértices adyacentes que tengan el mismo color. Por otro lado, G tiene un número lista-cromático 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é elección se haga de un color de la lista de A y un color de la lista de B , habrá algún otro vértice tal que ambas opciones ya se utilicen para colorear a sus vecinos. Por lo tanto, G no se puede elegir entre 2 opciones.
Por otro lado, es fácil ver que G se puede elegir entre tres opciones: 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 se pueden elegir arbitrariamente.
De manera más general, sea q un número entero positivo y sea G el gráfico bipartito completo K q , q q . Deje que los colores disponibles estén representados por los q 2 números diferentes de dos dígitos en la base q . En un lado de la bipartición, supongamos que a los q vértices se les den 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 opciones posibles de la primer dígito i . En el otro lado de la bipartición, supongamos que a los q q vértices se les den conjuntos de colores {0 a , 1 b , 2 c , ... } en los que los primeros dígitos son todos distintos, para cada una de las q q posibles opciones 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 de 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} tiene el color 01 y el vértice con el conjunto de colores {10,11} tiene el color 10, entonces el vértice con el conjunto de colores {01,10} no se puede colorear. Por lo tanto, el número cromático lista de G es al menos q + 1. [2]
De manera similar, si , entonces el gráfico bipartito completo K n , n no es k -seleccionable. Porque, supongamos que hay 2 k − 1 colores 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 se usan al menos k colores en un lado y al menos k 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 gráfico de utilidad K 3,3 tiene un número cromático de lista de al menos tres, y el gráfico K 10,10 tiene un número cromático de lista de al menos cuatro. [3]
Para un gráfico G , sea χ( G ) el número cromático y Δ( G ) el grado máximo de G . El número de coloración de la lista ch( G ) satisface las siguientes propiedades.
En la literatura se han considerado dos problemas algorítmicos:
Se sabe que la capacidad de elección k en gráficos bipartitos es completa para cualquier k ≥ 3, y lo mismo se aplica a la capacidad de elección 4 en gráficos planos, la capacidad de elección 3 en gráficos planos sin triángulos y la capacidad de elección (2, 3) en gráficos bipartitos. gráficos planos bipartitos . [9] [10] Para gráficos libres de P 5 , es decir, gráficos que excluyen un gráfico de ruta de 5 vértices , la capacidad de elección k es manejable con parámetros fijos . [11]
Es posible probar si un gráfico tiene 2 opciones de elección en tiempo lineal eliminando repetidamente los vértices de grado cero o uno hasta llegar al núcleo 2 del gráfico, después de lo cual ya no son posibles más eliminaciones. El gráfico inicial se puede elegir entre dos opciones si y solo si sus dos núcleos son un ciclo par o un gráfico theta formado por tres rutas con puntos finales compartidos, con dos rutas de longitud dos y la tercera ruta con una longitud par. [3]
La coloración de listas surge en problemas prácticos relacionados con la asignación de canales/frecuencias. [12] [13]
Otras lecturas
