En teoría de grafos , la coloración completa es lo opuesto a la coloración armoniosa en el sentido de que es una coloración de vértice 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.
Teoría de la complejidad
Encontrar ψ (G) es un problema de optimización . El problema de decisión para la coloración completa puede expresarse como:
- INSTANCIA: un gráfico y entero positivo
- PREGUNTA: ¿existe una partición de dentro o conjuntos más inconexos tal que cada es un conjunto independiente para y tal que para cada par de conjuntos distintos no es un conjunto independiente.
La determinación del número acromático es NP-difícil ; 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 emparejamiento mínimo máximo. [1]
Tenga en cuenta que cualquier coloración de un gráfico con la cantidad mínima de colores debe ser una coloración completa, por lo que minimizar la cantidad de colores en una coloración completa es solo una reafirmació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 una aproximación y es aproximado dentro de un relación de aproximación . [3]
Clases especiales de gráficos
El NP-completitud del problema de números acromáticos también es válido 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] cografías 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 árboles, se puede aproximar dentro de un factor constante. [3]
Se sabe que el número acromático de un gráfico de hipercubo n- dimensional es proporcional a, pero la constante de proporcionalidad no se conoce con precisión. [7]
Referencias
- ^ a b Michael R. Garey y David S. Johnson (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 978-0-7167-1045-5 A1.1: GT5, pág.191.
- ^ a b Farber, M .; Hahn, G .; Hell, P .; Miller, DJ (1986), "Concerning the achromatic number of graphs", Journal of Combinatorial Theory, Serie B , 40 (1): 21–39, doi : 10.1016 / 0095-8956 (86) 90062-6.
- ^ a b 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 cografías y gráficos de intervalo", Inf. Proceso. Letón. , 31 (3): 135–138, doi : 10.1016 / 0020-0190 (89) 90221-4 , hdl : 1874/16576.
- ^ Manlove, 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), "Edge dominating sets in graphs", SIAM Journal on Applied Mathematics , 38 (3): 364–372, doi : 10.1137 / 0138030.
- ^ Roichman, Y. (2000), "Sobre el número acromático de 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 de NP
- Una bibliografía de coloraciones armoniosas y números acromáticos por Keith Edwards