Lista para colorear

En la teoría de grafos , una rama de las matemáticas , la coloración por lista es un tipo de coloración de grafos donde cada vértice puede restringirse a una lista de colores permitidos. Fue estudiada 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 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 a cada vértice v un color de la lista L ( v ) . Al igual que con la coloración de grafos, se suele asumir que una coloración de lista es propia , lo que significa que no hay dos vértices adyacentes con el mismo color. Un grafo es k- elegible (o k -coloreable por lista ) si tiene una coloración de lista propia, independientemente de cómo se asigne una lista de k colores a cada vértice. La elegabilidad (o colorabilidad por 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 por lista independientemente de cómo se asigne una lista de f ( v ) colores a cada vértice v . En particular, si f ( v ) = k para todos los vértices v , la f -elegibilidad corresponde a la k- elegibilidad.

Consideremos 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 conectados cada uno a todos los W , X , Y , y ningún otro vértice está conectado. Como grafo bipartito, G tiene el número cromático usual 2: se puede colorear A y B de un color y W , X , Y , Z de otro y ningún par de vértices adyacentes tendrán el mismo color. Por otro lado, G tiene un número cromático de lista mayor que 2, como muestra la siguiente construcción: asignar a A y B las listas {rojo, azul} y {verde, negro}. Asignar a los otros cuatro vértices las listas {rojo, verde}, {rojo, negro}, {azul, verde} y {azul, negro}. Sin importar qué color se elija de la lista A o de la lista B , siempre habrá otro vértice cuyos colores ya estén utilizados para colorear a sus vecinos. Por lo tanto, G no es 2-elegible.

Por otro lado, es fácil ver que G es 3-elegible: al elegir colores arbitrarios para los vértices A y B, queda al menos un color disponible para cada uno de los vértices restantes, y estos colores pueden elegirse arbitrariamente.

De forma 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 ² números de dos dígitos diferentes 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 son 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 son 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 coloración de lista para L : independientemente del conjunto de colores que se elija para los vértices del lado pequeño de la bipartición, esta elección entrará en conflicto con todos los colores de uno de los vértices del otro lado de la bipartición. Por ejemplo, si el vértice con el conjunto de colores {00,01} se colorea con 01, y el vértice con el conjunto de colores {10,11} se colorea con 10, entonces el vértice con el conjunto de colores {01,10} no puede colorearse. Por lo tanto, el número cromático de lista de G es al menos q + 1. ^{[ 2 ]}

De manera similar, si${\displaystyle n={\tbinom {2k-1}{k}},}$Entonces, el grafo bipartito completo K _n,n no es k- elegible. 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 de estos colores diferente a la de 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 grafo de utilidad K _3,3 tiene un número cromático de lista de al menos tres, y el grafo K _10,10 tiene un número cromático de lista de 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.

1. ch( G ) ≥ χ ( G ) . Un grafo k -coloreable por lista debe tener en particular una coloración por lista cuando a cada vértice se le asigna la misma lista de k colores, lo que corresponde a una k -coloración usual.
2. En general, ch( G ) no puede acotarse en términos del número cromático; es decir, no existe ninguna función f tal que ch( G ) ≤ f ( χ ( G )) se cumpla para todo grafo G. En particular, como muestran los ejemplos de grafos bipartitos completos, existen grafos con χ ( G ) = 2 pero con ch( G ) arbitrariamente grande. ^{[ 2 ]}
3. ch( G ) ≤ χ ( G ) ln( n ) donde n es el número de vértices de G . ^{[ 4 ] [ 5 ]}
4. ch( G ) ≤ Δ( G ) + 1 . ^{[ 3 ] [ 6 ]}
5. ch( G ) ≤ 5 si G es un grafo planar . ^{[ 7 ]}
6. ch( G ) ≤ 3 si G es un grafo planar bipartito . ^{[ 8 ]}

En la literatura se han considerado dos problemas algorítmicos:

1. k - elegibilidad : decide si un grafo dado es k - elegible para un k dado y
2. ( a , b ) - elegibilidad : decide si un gráfico dado es f -elegible para una función dada.${\displaystyle f:V\to \{a,\dots ,b\}}$.

Se sabe que la k -elección en grafos bipartitos es${\displaystyle \Pi _{2}^{p}}$-completa para cualquier k ≥ 3 , y lo mismo se aplica para la 4-elección en grafos planares, la 3-elección en grafos planares libres de triángulos y la (2, 3)-elección en grafos planares bipartitos . ^{[ 9 ] [ 10 ]} Para grafos P ₅ -libres, es decir, grafos que excluyen un grafo de camino de 5 vértices , la k - elección es tratable 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 del cual ya no es posible realizar más eliminaciones. 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 extremos comunes, con dos caminos de longitud dos y el tercer camino de cualquier longitud par. ^{[ 3 ]}

La coloración de listas surge en problemas prácticos relacionados con la asignación de canales/frecuencias. ^{[ 12 ] [ 13 ]}

• coloración de bordes de lista

Lecturas adicionales

• Aigner, Martín; Ziegler, Günter (2009), Pruebas de THE BOOK (4ª  ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-642-00855-9, Capítulo 34 Cinco colores para grafos planos .
• Diestel, Reinhard. Teoría de grafos . 3.ª edición, Springer, 2005. Capítulo 5.4 Coloreado de listas . Edición electrónica disponible para descargar.