Coloración de lista

En teoría de grafos , la coloración de listas es una coloración de los vértices de una gráfica donde el color de cada vértice se restringe a una lista de colores autorizados. Fue estudiado por primera vez en la década de 1970 en artículos independientes de Vadim G. Vizing y de Paul Erdős , Arthur Rubin (en) y Herbert Taylor.

Definición

Dado un gráfico G y un conjunto de colores para cada vértice s (llamado su lista ), la coloración de la lista es una función que asigna cada vértice sa un color en la lista . Al igual que con el color habitual de los gráficos, generalmente se supone que el color de una lista es limpio , lo que significa que dos vértices adyacentes no tienen el mismo color. Un gráfico es k -selectable (o k -colorizable por lista ) si admite la coloración de lista adecuada, independientemente de la forma en que las listas de k colores se asignan a cada vértice. La choisissabilité (o lista de colorabilidad o lista de índice cromático ) ch ( G ) de un gráfico G es el número más pequeño k tal que G es k -eleccionable. $L (s)$ $L (s)$

De manera más general, una función para asignar un número entero positivo en cada cima , un gráfico G es -elegible (o -Coloriable List ) si es una lista de colores que asigna una lista de colores en cada vértice . En particular, si para todos los vértices , entonces la -seleccionabilidad corresponde a la k -seleccionabilidad. $F$ $f (s)$ $s$ $F$ $F$ $f (s)$ $s$ ${\ Displaystyle f (s) = k}$ $s$ $F$

Ejemplos de

Consideramos el grafo bipartito completo con seis vértices A , B , W , X , Y , Z cuya partición está compuesta por A y B y por W , X , Y y Z por otro lado; los vértices A y B están conectados a todos los vértices W , X , Y y Z , y no hay otros bordes. Como gráfico bipartito, el índice cromático habitual de G es 2: podemos colorear A y B con el mismo color y W , X , Y , Z con los mismos otros colores; por tanto, dos vértices adyacentes no tienen el mismo color. Por otro lado, G tiene un índice cromático de lista mayor que 2, como lo muestra la siguiente construcción: asignamos a A y B las listas {rojo, azul} y {verde, negro} y asignamos a los otros cuatro vértices el listas {rojo, verde}, {rojo, negro}, {azul, verde} y {azul, negro}. Cualquiera que sea la elección de color realizada en la lista de A y en la lista de B , uno de los otros 4 vértices tiene entre sus dos opciones posibles solo los colores ya utilizados para colorear a sus vecinos. Por lo tanto, G no es seleccionable en 2 ocasiones. ${\ Displaystyle G = K_ {2,4}}$

Por otro lado, es fácil ver que G es 3-seleccionable: elegimos colores arbitrarios para los vértices A y B ; al menos un color permanece disponible para cada uno de los otros vértices, 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 . Se supone que hay colores disponibles que están representados por números distintos de dos dígitos en la base q . Para el componente con q vértices de la bipartición, le damos a los q vértices los conjuntos de colores donde los primeros dígitos son todos iguales, para las q posibles elecciones del primer dígito . Para el otro componente de la bipartición, damos a los vértices conjuntos de colores en los que los primeros dígitos son todos distintos, para cada una de las posibles opciones del q -uplet , donde se ejecutan todos los valores posibles. La figura en la parte superior de la página muestra un ejemplo de la construcción de . ${\ Displaystyle K_ {q, q ^ {q}}}$ $q ^ {2}$ $q ^ {2}$ ${\ Displaystyle \ {i0, i1, i2, \ ldots \}}$ $I$ ${\ Displaystyle q ^ {q}}$ ${\ Displaystyle \ {0a, 1b, 2c \ ldots \}}$ ${\ Displaystyle q ^ {q}}$ ${\ Displaystyle \ {0a, 1b, 2c \ ldots \}}$ ${\ Displaystyle a, b, c \ ldots}$ ${\ Displaystyle q = 3}$

Con esta construcción, el gráfico G no tiene colores de lista para estos colores: cualquiera que sea el conjunto de colores elegido para los q vértices en el lado corto de la bipartición, esta elección entra en conflicto con todos los colores para l 'uno de los picos del otro. lado de la bipartición. Por ejemplo, si para q = 2, el vértice con el conjunto de colores {00.01} se colorea en 01, y el vértice con el conjunto de colores {10.11} se colorea en 10, entonces el vértice con el conjunto de colores {01.10} no se puede de colores. Por lo tanto, el índice cromático de lista de G es al menos . $q + 1$

Del mismo modo, si , entonces el gráfico bipartito completo no es k -seleccionable. Supongamos que los colores están disponibles en total y que, en uno de los lados de la bipartición, cada vértice tiene a su disposición una k -tupla de estos colores, diferentes entre sí. Entonces, cada lado de la bipartición debe usar al menos k colores, porque cada conjunto de colores está separado 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 rompecabezas de tres casas tiene un índice de color de lista de al menos tres, y el gráfico tiene un índice de color de lista de al menos cuatro. ${\ Displaystyle n = {\ binom {2k-1} {k}}}$ ${\ Displaystyle K_ {n, n}}$ ${\ Displaystyle 2k-1}$ $k-1$ $K_ {3.3}$ ${\ Displaystyle K_ {10.10}}$

Propiedades

Para un gráfico G , tenga en cuenta el índice de color y el grado máximo de G . El índice cromático de la lista de canales tiene las siguientes propiedades: $\ chi (G)$ $\ Delta (G)$ ${\ Displaystyle (G)}$

ch . Un gráfico de lista con k colores debe tener, en particular, un color de lista cuando a cada vértice se le asigna la misma lista de k colores, lo que corresponde a un color de k habitual. ${\ Displaystyle (G) \ geq \ chi (G)}$
HP no puede generalmente ser limitada dependiendo del índice de color, es decir que no hay ninguna función como ch comprobarse por cualquier gráfico G . En particular, como muestran los ejemplos de gráficos bipartitos completos, hay gráficos con pero con un ch arbitrariamente grande. ${\ Displaystyle (G)}$ $F$ ${\ Displaystyle (G) \ leq f (\ chi (G)}$ ${\ Displaystyle \ chi (G) = 2}$ ${\ Displaystyle (G)}$
ch , donde n es el número de vértices de G . ${\ Displaystyle (G) \ leq \ chi (G) \ log \, n}$
ch si G es un gráfico plano . ${\ Displaystyle (G) \ leq 5}$
ch si G es un gráfico plano bipartito . ${\ Displaystyle (G) \ leq 3}$

Cálculo de seleccionabilidad y ( a , b ) -seleccionabilidad

Se consideraron los siguientes problemas algorítmicos:

$k$ -seleccionabilidad : decide si un gráfico dado es k -seleccionable para un k dado, y
$(a, b)$ - choosability : decidir si un grafo dado es f- choosable para una función dada . ${\ Displaystyle f: V \ to \ {a, \ dots, b \}}$

Sabemos que la k -seleccionabilidad en gráficas bipartitas es -completa para todo , y es la misma para la 4-seleccionabilidad en gráficas planas, la 3-seleccionabilidad en gráficas planas sin triángulo y la (2, 3) -seleccionabilidad en bipartitas gráficos planares . Para gráficos sin P 5 , es decir, gráficos que excluyen trayectos con 5 vértices, la k -seleccionabilidad es tratable con un parámetro fijo . ${\ Displaystyle \ Pi _ {2} ^ {p}}$ ${\ Displaystyle k \ geq 3}$

Es posible probar si un gráfico es 2-seleccionable en tiempo lineal eliminando sucesivamente vértices de grado cero o uno hasta llegar al 2-kernel del gráfico, después de lo cual tales eliminaciones no son posibles. El gráfico inicial es 2-seleccionable si y solo si su 2-kernel es un ciclo par o un gráfico theta que está formado por tres caminos con extremos compartidos, donde dos caminos tienen una longitud de dos y el tercer camino de longitud uniforme.

Aplicaciones

La coloración de la lista surge en cuestiones prácticas relacionadas con la asignación de canal / frecuencia

Notas y referencias

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado " Coloración de listas " ( consulte la lista de autores ) .

Vadim G. Vizing, “ colorantes vértice con los colores indicados (en ruso) ”, Metody Diskret. Analiz. , vol. 29,1976, p. 3-10 ( zbMATH 0362.05060 )
Paul Erdös, Arthur Rubin y Herbert Taylor, “Choosability en los gráficos” , en Proc. Conf. Costa Oeste sobre combinatoria, teoría de grafos y computación (Humboldt State Univ., Arcata, Calif., 1979) , coll. "Congressus Numerantium" ( n o XXVI)1980( Math Reviews 0593902 , leer en línea ) , pág. 125-157.
Tommy R. Jensen y Bjarne Toft , Problemas de coloración de gráficos , Nueva York, Wiley-Interscience,2011, 2 nd ed. ( ISBN 0-471-02865-7 ) , pág. 1.9 Lista de colores: páginas = 18-21.
Traducción de "choosable" con "choisissable" y sustantivos asociados ratificado por choisissabilité en el wikcionario
Sylvain Gravier , " Un teorema similar a Hajós para colorear listas ", Matemáticas discretas , vol. 152, n hueso 1-3,1996, p. 299–302 ( DOI 10.1016 / 0012-365X (95) 00350-6 , Revisiones de matemáticas 1388650 ).
Carsten Thomassen , “ Cada gráfico planar se puede elegir entre 5 ” , Journal of Combinatorial Theory, Serie B , vol. 62,1994, p. 180–181 ( DOI 10.1006 / jctb.1994.1062 ).
Noga Alon y Michael Tarsi , “ Colorantes y orientaciones de gráficos ”, Combinatorica , vol. 12, n o 21992, p. 125-134 ( DOI 10.1007 / BF01204715 )
Shai Gutner , " La complejidad de la posibilidad de elegir un gráfico plano " , Matemáticas discretas , vol. 159, n o 1,1996, p. 119–130 ( DOI 10.1016 / 0012-365X (95) 00104-5 , arXiv 0802.2668 ).
Shai Gutner y Michael Tarsi , " Algunos resultados sobre ( a : b ) -elegibilidad ", Matemáticas discretas , vol. 309, n o 8,2009, p. 2260–2270 ( DOI 10.1016 / j.disc.2008.04.061 ).
Pinar Heggernes y Petr Golovach , " Elección de gráficos libres de P 5 ", Notas de la conferencia sobre informática , Springer-Verlag, vol. 5734 "Fundamentos matemáticos de la informática",2009, p. 382–391 ( leer en línea ).
Wei Wang y Xin Liu , “ Asignación de canales basada en coloración de listas para redes inalámbricas de espectro abierto ”, 62ª Conferencia de Tecnología Vehicular de la IEEE 2005 (VTC 2005-Otoño) , vol. 1,2005, p. 690–694 ( DOI 10.1109 / VETECF.2005.1558001 ).
N. Garg , M. Papatriantafilou y P. Tsigas , " Coloración de listas distribuidas: cómo asignar frecuencias dinámicamente a estaciones base móviles ", Octavo Simposio IEEE sobre procesamiento paralelo y distribuido ,1996, p. 18-25 ( DOI 10.1109 / SPDP.1996.570312 , hdl 21.11116 / 0000-0001-1AE6-F ).
Jean-Sébastien Sereni, Aplicación y coloración de gráficos: modelado y simulación , Universidad de Niza Sophia Antipolis, coll. " Tesis de doctorado ",2006( HAL tel-00120594 ).

Bibliografía

Aigner, Martin y Ziegler, Günter, Proofs from THE BOOK , Berlín, Nueva York, Springer-Verlag,2009( ISBN 978-3-642-00855-9 ) , Capítulo 34 Gráficos planos de cinco colores.
Reinhard Diestel, teoría de grafos , Springer-Verlag, Heidelberg, coll. "Textos de Posgrado en Matemáticas" ( n o 173)2016, 447 p. ( ISBN 978-3-662-53621-6 y 978-3-96134-005-7 , leer en línea ).