Coloração completa

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.

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

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

QUESTÃO: será que existe uma partição de ${\displaystyle V}$ em ${\displaystyle k}$ ou mais conjuntos disjuntos ${\displaystyle V_{1},V_{2},\ldots ,V_{k}}$, tal que cada ${\displaystyle V_{i}}$ é um conjunto independente para ${\displaystyle G}$ e tal que, para cada par de conjuntos distintos ${\displaystyle V_{i},V_{j}}$, ${\displaystyle 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.^[1]

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.

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

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

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

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

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

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