Coloración completa

En teoría de grafos , una coloración completa es una coloración de vértices (propia) en la que cada par de colores aparece en al menos un par de vértices adyacentes . De forma equivalente, una coloración completa es mínima en el sentido de que no puede transformarse en una coloración propia con menos colores mediante la fusión de 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.

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

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 ₁ , V ₂ , …, V _k tal 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 demostraron Yannakakis y Gavril en 1978 mediante una transformación del problema de coincidencia máxima mínima. ^{[ 1 ]}

Cabe señalar que cualquier coloración de un grafo con el número mínimo de colores debe ser una coloración completa, por lo que minimizar el número de colores en una coloración completa es simplemente una reformulación del problema estándar de coloración de grafos .

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 un margen de error.${\displaystyle O\left(|V|/{\sqrt {\log |V|}}\right)}$relación de aproximación . ^{[ 3 ]}

La NP-completitud del problema del número acromático también se cumple 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 complementos de árboles, el número acromático se puede calcular en tiempo polinomial. ^{[ 6 ]} Para árboles, se puede aproximar con un factor constante. ^{[ 3 ]}

Se sabe que el número acromático de un grafo hipercubo n -dimensional es proporcional a${\displaystyle {\sqrt {n2^{n}}}}$, pero la constante de proporcionalidad no se conoce con precisión. ^{[ 7 ]}

• Un compendio de problemas de optimización NP
• Bibliografía sobre colores armoniosos y números acromáticos, por Keith Edwards.