Coloração completa

Coloração completa do grafo de Clebsch com 8 cores. Todo par de cores aparece em pelo menos uma aresta. Não existe coloração completa com mais cores: em qualquer 9-coloração, alguma cor apareceria apenas em um vértice, e não haveria vértices vizinhos suficientes para cobrir todos os pares envolvendo essa cor. Portanto, o número acromático de um grafo Clebsch é 8.

Em teoria dos grafos, coloração completa é o oposto de coloração harmoniosa no sentido de que ele é uma coloração de vértices em que cada par de cores aparece em pelo menos um par de vértices adjacentes. Equivalentemente, uma Coloração Completa é mínima, no sentido de que ela não pode ser transformada em uma coloração adequada com menos cores, mesclando pares de classes de cor. O número acromático ψ(G) de um grafo G é número máximo de cores possível em qualquer Coloração Completa de G.

Teoria da complexidade

Encontrar ψ(G) é um problema de otimização. O problema de decisão para coloração completa pode ser expressa como:

INSTÂNCIA: um grafo $G=(V,E)$ e um inteiro positivo $k$

QUESTÃO: será que existe uma partição de $V$ em $k$ ou mais conjuntos disjuntos $V_{1},V_{2},\ldots ,V_{k}$, tal que cada $V_{i}$ é um conjunto independente para $G$ e tal que, para cada par de conjuntos distintos $V_{i},V_{j}$, $V_{i}\cup V_{j}$ não é um conjunto independente.

Determinar um número acromático é NP-difícil; determinar se ele é maior do que um dado número é NP-completo, como mostrado por Yannakakis e Gavril em 1978 pela transformação do problema da mínima correspondência máxima.

Note que qualquer coloração de um grafo com o número mínimo de cores deve ser uma Coloração Completa. Portanto, minimizar o número de cores na Coloração Completa é apenas uma atualização do problema da coloração de grafos padrão.

Algoritmos

Para qualquer k fixo, é possível determinar se o número acromático de um dado grafo é pelo menos k, em tempo linear.

O problema de otimização permite aproximação e é aproximável em uma taxa de aproximação $O\left(|V|/{\sqrt {\log |V|}}\right)$.

Classes especiais de grafos

A NP-completude do problema do número acromático vale também para algumas classe especiais de grafos: grafos bipartidos, complementares de grafos bipartidos (isto é, grafos que não têm conjunto independente de mais do que dois vértices), cografos e grafos de intervalo, e até para árvores.

Para complementos de árvores, o número acromático pode ser computado em tempo polinomial. Para árvores, ele pode ser aproximado para um fator constante.

O número acrómático de um grafo de hipercubo n-dimensional é conhecido por ser proporcional à ${\sqrt {n2^{n}}}$, mas a constante de proporcionalidade não é precisamente conhecida.

Ligações externas

• A compendium of NP optimization problems
• A Bibliography of Harmonious Colourings and Achromatic Number por Keith Edwards