Mostrar código-fonte de Coloração completa

[[Image:Complete coloring clebsch graph.svg|right|300px|thumb|
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 grafos|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 <math>G=(V,E)</math> e um inteiro positivo <math>k</math>
:QUESTÃO: será que existe uma [[partição de um conjunto|partição]] de <math>V</math> em <math>k</math> ou mais [[conjuntos disjuntos]] <math>V_1,V_2,\ldots,V_k</math>, tal que cada <math>V_i</math> é um [[conjunto independente]] para <math>G</math> e tal que, para cada par de conjuntos distintos <math>V_i,V_j</math>, <math>V_i \cup V_j</math> 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.<ref name="gj">{{Citation|autor = [[Michael R. Garey]] and [[David S. Johnson]] |ano= 1979 |título= Computers and Intractability: A Guide to the Theory of NP-Completeness |publicado= W.H. Freeman | isbn = 0-7167-1045-5}} A1.1: GT5, pg.191.</ref>

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.<ref name="fhhm"/>

O problema de otimização permite aproximação e é aproximável em uma [[algoritmo de aproximação|taxa de aproximação]] <math>O\left(|V|/\sqrt{\log |V|}\right)</math>.<ref name="cv">{{citation|último1 =Chaudhary|primeiro1 =Amitabh|último2 =Vishwanathan|primeiro2 =Sundar|título=Approximation algorithms for the achromatic number|periódico=Journal of Algorithms|volume=41|ano=2001|número=2|páginas=404–416|doi=10.1006/jagm.2001.1192}}.</ref>

==Classes especiais de grafos==
A NP-completude do problema do número acromático vale também para algumas classe especiais de grafos:
[[grafo bipartido|grafos bipartidos]],<ref name="fhhm">{{citation|último1 =Farber|primeiro1 =M.|último2 =Hahn|primeiro2 =G.|último3 =Hell|primeiro3 =P.|autorlink3 =Pavol Hell|último4 =Miller|primeiro4 =D. J.|título=Concerning the achromatic number of graphs|periódico=Journal of Combinatorial Theory, Series B|volume=40|número=1|ano=1986|páginas=21–39|doi=10.1016/0095-8956(86)90062-6}}.</ref>
[[grafo complementar|complementares]] de [[grafo bipartido|grafos bipartidos]] (isto é, grafos que não têm conjunto independente de mais do que dois vértices),<ref name="gj"/> [[cografo]]s e [[grafo de intervalo|grafos de intervalo]],<ref>{{citation|último =Bodlaender|primeiro =H.|autorlink =Hans L. Bodlaender|título=Achromatic number is NP-complete for cographs and interval graphs|periódico=Inform. Proc. Lett.|volume=31|ano=1989|número=3|páginas=135–138|doi=10.1016/0020-0190(89)90221-4}}.</ref> e até para árvores.<ref>{{citation|último1 =Manlove|primeiro1 =D.|último2 =McDiarmid|primeiro2 =C.|título=The complexity of harmonious coloring for trees|periódico=Discrete Applied Mathematics|volume=57|ano=1995|número=2-3|páginas=133–144|doi=10.1016/0166-218X(94)00100-R}}.</ref>

Para complementos de árvores, o número acromático pode ser computado em tempo polinomial.<ref>{{citation|último1 =Yannakakis|primeiro1 =M.|último2 =Gavril|primeiro2 =F.|título=Edge dominating sets in graphs|periódico=SIAM Journal on Applied Mathematics|volume=38|ano=1980|número=3|páginas=364–372|doi=10.1137/0138030}}.</ref> Para árvores, ele pode ser aproximado para um fator constante.<ref name="cv"/>

O número acrómático de um [[grafo de hipercubo]] ''n''-dimensional é conhecido por ser proporcional à <math>\sqrt{n2^n}</math>, mas a constante de proporcionalidade não é precisamente conhecida.<ref>{{citation|último =Roichman|primeiro =Y.|título= On the Achromatic Number of Hypercubes|periódico=Journal of Combinatorial Theory, Series B|volume=79|número=2|ano=2000|páginas=177–182|doi=10.1006/jctb.2000.1955}}.</ref>

==Referências==
{{reflist|2}}

== Ligações externas ==
* [http://www.nada.kth.se/~viggo/wwwcompendium/node17.html A compendium of NP optimization problems]
* [https://web.archive.org/web/20040707113436/http://www.maths.dundee.ac.uk/~kedwards/biblio.html ''A Bibliography of Harmonious Colourings and Achromatic Number''] por Keith Edwards

{{DEFAULTSORT:Coloracao Completa}}
[[Categoria:Coloração de grafos]]
[[Categoria:Invariantes de grafos]]