En la teoría de grafos , una rama de las matemáticas , la coloración de listas es un tipo de coloración de gráficos en la que 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 por Vizing y por Erdős , Rubin y Taylor. [1]
Definición
Dado un gráfico G y dado un conjunto L ( v ) de colores para cada vértice v (llamado lista ), un color 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 -eleccionable (o k -lista-colorante ) si tiene un color de lista adecuado sin importar cómo se asigne una lista de k colores a cada vértice. La posibilidad de elección (o la colorabilidad de la lista o el número cromático de la lista ) ch ( G ) de un gráfico G es el menor número k tal que G es k elegible.
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 -elegable (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, sipara todos los vértices v , f -elegibilidad corresponde a k -elegibilidad.
Ejemplos de
Considere el gráfico bipartito completo G = K 2,4 , que tiene seis vértices A , B , W , X , Y , Z de manera que A y B están conectados a todos los W , X , Y y Z , y no a otros vértices. estan conectados. Como gráfico bipartito, G tiene el número cromático habitual 2: uno puede 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 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}. Independientemente de la elección que se haga de un color de la lista de A y de un color de la lista de B , habrá algún otro vértice tal que sus dos opciones ya se utilicen para colorear a sus vecinos. Por lo tanto, G no se puede elegir entre 2.
Por otro lado, es fácil ver que G tiene 3 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 pueden elegirse arbitrariamente.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/e/e8/List-coloring-K-3-27.svg/300px-List-coloring-K-3-27.svg.png)
De manera más general, sea q un número entero positivo y sea G el gráfico bipartito completo K q , q q . Dejemos que los colores disponibles estén representados por q 2 números diferentes de dos dígitos en la base q . En un lado de la bipartición, damos a 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 opciones de la primer dígito i . En el otro lado de la bipartición, sean los q q vértices dados 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 un color de lista 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} tiene el color 01 y el vértice con el conjunto de colores {10,11} está coloreado con 10, entonces el vértice con el conjunto de colores {01,10} no se puede colorear. Por lo tanto, el número cromático de la lista de G es al menos q + 1. [2]
Del mismo modo, si , entonces el grafo bipartito completo K n , n no es k elegible. Para, suponga 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á desarticulado de la lista de un vértice. Dado que se usan al menos k colores 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 gráfico de utilidad K 3,3 tiene un número cromático de lista al menos tres, y el gráfico K 10,10 tiene un número cromático de lista al menos cuatro. [3]
Propiedades
Para un gráfico G , dejar que χ ( G ) denotan el número cromática y Δ ( G ) el grado máximo de G . El número de coloración de lista ch ( G ) satisface las siguientes propiedades.
- ch ( G ) ≥ χ ( G ). Un grafo colorante de k -list debe tener, en particular, un color de lista cuando a cada vértice se le asigna la misma lista de k colores, que corresponde a un k -coloring habitual .
- ch ( G ) no puede ser limitada en términos de número cromática en general, es decir, no hay una función f tal que ch ( G ) ≤ f (χ ( G )) se mantiene para cada gráfico G . En particular, como muestran los ejemplos completos de gráficos bipartitos, existen gráficos con χ ( G ) = 2 pero con ch ( G ) arbitrariamente grande. [2]
- ch ( G ) ≤ χ ( G ln) ( n ), donde n es el número de vértices de G . [4] [5]
- ch ( G ) ≤ Δ ( G ) + 1. [3] [6]
- ch ( G ) ≤ 5 si G es un gráfico plano . [7]
- ch ( G ) ≤ 3 si G es un gráfico plano bipartito . [8]
Elección de computación y ( a , b ) -elegibilidad
En la literatura se han considerado dos problemas algorítmicos:
- k - elegibilidad : decide si un gráfico dado es k - elegible para un k dado , y
- ( a , b ) - posibilidad de elección : decide si una gráfica determinada es f -eleccionable para una función determinada.
Se sabe que k -elegibilidad en grafos bipartitos es-completo para cualquier k ≥ 3, y lo mismo se aplica para 4 opciones en gráficos planos, 3 opciones en gráficos planos libres de triángulos y (2, 3) opciones en gráficos bipartitos planos. [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 opción k es manejable con parámetros fijos . [11]
Es posible probar si un gráfico se puede elegir en 2 en tiempo lineal eliminando repetidamente los vértices de grado cero o uno hasta alcanzar los 2 núcleos del gráfico, después de lo cual no son posibles más eliminaciones de este tipo. El gráfico inicial se puede elegir entre 2 si y solo si su 2 núcleos es 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 cualquier longitud uniforme. [3]
Aplicaciones
La coloración de listas surge en problemas prácticos relacionados con la asignación de canal / frecuencia. [12] [13]
Ver también
Referencias
- ^ Jensen, Tommy R .; Toft, Bjarne (1995), "1.9 Coloración de listas", Problemas de coloración de gráficos , Nueva York: Wiley-Interscience, págs. 18-21, ISBN 0-471-02865-7
- ^ a b Gravier, Sylvain (1996), "Un teorema similar a Hajós para colorear listas", Matemáticas discretas , 152 (1-3): 299-302, doi : 10.1016 / 0012-365X (95) 00350-6 , MR 1388650.
- ^ a b c Erdős, P .; Rubin, AL ; Taylor, H. (1979), "Elección en gráficos", Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata (PDF) , Congressus Numerantium, 26 , págs. 125-157, archivado desde el original (PDF) el 2016-03-09 , consultado el 2008-11-10
- ^ Eaton, Nancy (2003), "En dos pruebas breves sobre coloración de listas - Parte 1" (PDF) , Charla , archivado del original (PDF) el 29 de agosto de 2017 , consultado el 29 de mayo de 2010
- ^ Eaton, Nancy (2003), "En dos pruebas breves sobre coloración de listas - Parte 2" (PDF) , Charla , archivado del original (PDF) el 30 de agosto de 2017 , consultado el 29 de mayo de 2010
- ^ Vizing, VG (1976), " Coloreaciones de vértices con colores dados", Metody Diskret. Analiz. (en ruso), 29 : 3–10
- ^ Thomassen, Carsten (1994), "Cada grafo plano se puede elegir entre 5", Journal of Combinatorial Theory, Serie B , 62 : 180–181, doi : 10.1006 / jctb.1994.1062
- ^ Alon, Noga ; Tarsi, Michael (1992), "Coloreaciones y orientaciones de gráficos", Combinatorica , 12 (2): 125-134, doi : 10.1007 / BF01204715
- ^ Gutner, Shai (1996), "La complejidad de la elección de grafos planos", Matemáticas discretas , 159 (1): 119–130, arXiv : 0802.2668 , doi : 10.1016 / 0012-365X (95) 00104-5.
- ^ Gutner, Shai; Tarsi, Michael (2009), "Algunos resultados sobre ( a : b ) -elegibilidad", Matemáticas discretas , 309 (8): 2260-2270, doi : 10.1016 / j.disc.2008.04.061
- ^ Heggernes, Pinar ; Golovach, Petr (2009), "Elección de gráficos libres de P 5 " (PDF) , Fundamentos matemáticos de la informática , Notas de la conferencia sobre informática, 5734 , Springer-Verlag, págs. 382–391
- ^ Wang, Wei; Liu, Xin (2005), "Asignación de canales basada en listas de colores para redes inalámbricas de espectro abierto", 62ª Conferencia de tecnología vehicular de la IEEE 2005 (VTC 2005-Fall) , 1 , págs. 690–694, doi : 10.1109 / VETECF.2005.1558001.
- ^ Garg, N .; Papatriantafilou, M .; Tsigas, P. (1996), "Coloración de listas distribuidas: cómo asignar frecuencias dinámicamente a estaciones base móviles", Octavo Simposio IEEE sobre procesamiento paralelo y distribuido , págs. 18-25, doi : 10.1109 / SPDP.1996.570312 , hdl : 21.11116 / 0000-0001-1AE6-F.
Otras lecturas
- Aigner, Martin; Ziegler, Günter (2009), Proofs from THE BOOK (4a ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-642-00855-9, Capítulo 34 Gráficos planos de cinco colores .
- Diestel, Reinhard. Teoría de grafos . 3ª edición, Springer, 2005. Capítulo 5.4 Coloración de listas . edición electrónica disponible para descargar