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 -eleccionable (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 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é 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, dejemos que los q q vértices reciban 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 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 uno de los demás vértices. 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:
It is known that k-choosability in bipartite graphs is -complete for any k ≥ 3, and the same applies for 4-choosability in planar graphs, 3-choosability in planar triangle-free graphs, and (2, 3)-choosability in bipartite planar graphs.[9][10] For P5-free graphs, that is, graphs excluding a 5-vertex path graph, k-choosability is fixed-parameter tractable.[11]
It is possible to test whether a graph is 2-choosable in linear time by repeatedly deleting vertices of degree zero or one until reaching the 2-core of the graph, after which no more such deletions are possible. The initial graph is 2-choosable if and only if its 2-core is either an even cycle or a theta graph formed by three paths with shared endpoints, with two paths of length two and the third path having any even length.[3]
List coloring arises in practical problems concerning channel/frequency assignment.[12][13]
Otras lecturas
