Coloración de vértices donde cada combinación de colores aparece al menos una vez
Coloración completa del gráfico de Clebsch con 8 colores. Cada par de colores aparece al menos en un borde. No existe una coloración completa con más colores: en cualquier coloración de 9, algún color aparecería solo en un vértice y no habría suficientes vértices vecinos para cubrir todos los pares que involucran ese color. Por tanto, el número acromático de la gráfica de Clebsch es 8.
En teoría de grafos , una coloración completa es una coloración de vértices en la que cada par de colores aparece en al menos un par de vértices adyacentes . De manera equivalente, una coloración completa es mínima en el sentido de que no se puede transformar en una coloración adecuada con menos colores fusionando pares de clases de colores. El número acromático ψ( G ) de un gráfico G es el número máximo de colores posibles en cualquier coloración completa de G .
Una coloración completa es lo opuesto a una coloración armoniosa , que requiere que cada par de colores aparezca como máximo en un par de vértices adyacentes.
INSTANCIA: una gráfica G = ( V , E ) y un entero positivo k
PREGUNTA: ¿existe una partición de V en k o más conjuntos disjuntos V 1 , V 2 , …, V k tal que cada V i sea un conjunto independiente para G y tal que para cada par de conjuntos distintos Vi , V j , V i ∪ V j no es un conjunto independiente.
La determinación del número acromático es NP-duro ; determinar si es mayor que un número dado es NP-completo , como lo demostraron Yannakakis y Gavril en 1978 mediante la transformación del problema de coincidencia mínimo máximo. [1]
Tenga en cuenta que cualquier coloración de un gráfico con el número mínimo de colores debe ser una coloración completa, por lo que minimizar la cantidad de colores en una coloración completa es solo una reformulación del problema estándar de coloración de gráficos .
Algoritmos
Para cualquier k fijo , es posible determinar si el número acromático de un gráfico dado es al menos k , en tiempo lineal. [2]
El problema de optimización permite la aproximación y es aproximable dentro de una relación de aproximación . [3]
Clases especiales de gráficos.
La completitud NP del problema de números acromáticos también es válida para algunas clases especiales de gráficos: gráficos bipartitos , [2] complementos de gráficos bipartitos (es decir, gráficos que no tienen un conjunto independiente de más de dos vértices), [1] cografos e intervalos. gráficos , [4] e incluso para árboles. [5]
Para complementos de árboles, el número acromático se puede calcular en tiempo polinomial. [6] Para los árboles, se puede aproximar dentro de un factor constante. [3]
Se sabe que el número acromático de un gráfico de hipercubo de n dimensiones es proporcional a , pero la constante de proporcionalidad no se conoce con precisión. [7]
^ ab Farber, M.; Hahn, G.; Demonios, P .; Miller, DJ (1986), "Sobre el número acromático de gráficos", Journal of Combinatorial Theory, Serie B , 40 (1): 21–39, doi : 10.1016/0095-8956(86)90062-6.
^ ab Chaudhary, Amitabh; Vishwanathan, Sundar (2001), "Algoritmos de aproximación para el número acromático", Journal of Algorithms , 41 (2): 404–416, CiteSeerX 10.1.1.1.5562 , doi :10.1006/jagm.2001.1192, S2CID 9817850 .
^ Bodlaender, H. (1989), "El número acromático es NP-completo para cografos y gráficos de intervalo", Inf. Proceso. Letón. , 31 (3): 135–138, doi :10.1016/0020-0190(89)90221-4, hdl : 1874/16576.
^ Amor humano, D.; McDiarmid, C. (1995), "La complejidad de la coloración armoniosa de los árboles", Matemáticas Aplicadas Discretas , 57 (2–3): 133–144, doi : 10.1016/0166-218X(94)00100-R.
^ Yannakakis, M.; Gavril, F. (1980), "Conjuntos dominantes de bordes en gráficos", Revista SIAM de Matemáticas Aplicadas , 38 (3): 364–372, doi :10.1137/0138030.
^ Roichman, Y. (2000), "Sobre el número acromático de los hipercubos", Journal of Combinatorial Theory, Serie B , 79 (2): 177–182, doi : 10.1006/jctb.2000.1955.
enlaces externos
Un compendio de problemas de optimización NP.
Una bibliografía de colores armoniosos y números acromáticos de Keith Edwards
