stringtranslate.com

Coloración completa

Coloración completa del grafo de Clebsch con 8 colores. Cada par de colores aparece en al menos una arista. No existe una coloración completa con más colores: en cualquier coloración de 9 colores, 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 lo tanto, el número acromático del grafo de Clebsch es 8.

En teoría de grafos , una coloración completa es una coloración de vértices (adecuada) 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 color. El número acromático ψ( G ) de un grafo 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.

Teoría de la complejidad

Encontrar ψ( G ) es un problema de optimización . El problema de decisión para la coloración completa se puede formular de la siguiente manera:

INSTANCIA: un grafo 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 tales que cada V i sea un conjunto independiente para G y tal que para cada par de conjuntos distintos V i , V j , V i ∪ V j no sea un conjunto independiente?

Determinar el 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 coincidencia mínima-máxima. [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 simplemente una reformulación del problema de coloración de gráficos estándar .

Algoritmos

Para cualquier k fijo , es posible determinar si el número acromático de un grafo 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 NP-completitud del problema del número acromático se cumple también para algunas clases especiales de grafos: grafos bipartitos , [2] complementos de grafos bipartitos (es decir, grafos que no tienen un conjunto independiente de más de dos vértices), [1] cografos y grafos de intervalo , [4] e incluso para árboles. [5]

Para los 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 n -dimensional es proporcional a , pero la constante de proporcionalidad no se conoce con precisión. [7]

Referencias

  1. ^ ab Michael R. Garey y David S. Johnson (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, ISBN 978-0-7167-1045-5A1.1: GT5, pág.191.
  2. ^ ab Farber, M.; Hahn, G.; Hell, P .; Miller, DJ (1986), "Sobre el número acromático de grafos", Journal of Combinatorial Theory, Serie B , 40 (1): 21–39, doi : 10.1016/0095-8956(86)90062-6.
  3. ^ 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 .
  4. ^ Bodlaender, H. (1989), "El número acromático es NP-completo para cografos y grafos de intervalo", Inf. Process. Lett. , 31 (3): 135–138, doi :10.1016/0020-0190(89)90221-4, hdl : 1874/16576.
  5. ^ Manlove, D.; McDiarmid, C. (1995), "La complejidad de la coloración armoniosa de los árboles", Discrete Applied Mathematics , 57 (2–3): 133–144, doi : 10.1016/0166-218X(94)00100-R.
  6. ^ Yannakakis, M.; Gavril, F. (1980), "Conjuntos con aristas dominantes en grafos", SIAM Journal on Applied Mathematics , 38 (3): 364–372, doi :10.1137/0138030.
  7. ^ 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