right|300px|thumb| Coloração harmônica de uma 7-árvore com 3 níveis usando 12 cores. O numero harmônico cromático desse grafo é 12 já que são 57 vértices, e o pareamento de cores é ncor*(ncor-1)/2 >= 57 sse ncor>=12. Além disso (3/2)*(7+1)=12(veja a fórmula de Mitchem).
Em teoria dos grafos, uma coloração harmônica é uma coloração de vértices (própria) na qual todo emparelhamento de cores aparece em no máximo um par de vértices adjacentes. O Numero harmônico cromático χH(G) de um grafo G é o número mínimo de cores necessárias para qualquer coloração harmônica de G.
Cada grafo tem uma coloração harmônica, visto que é suficiente atribuír a cada vértica uma cor distinta; então χH(G) ≤ |V(G)|. Existem trivialmente grafos G com χH(G) > χ(G) (onde χ é o número cromático); um exemplo é um caminho de tamanho 2, o qual pode ser 2-colorado(colorido com 2 cores) mas não tem uma coloração harmônica com 2 cores.
Algumas propriedades de χH(G): χH(Tk,3) = ⌈(3/2)(k+1)⌉, onde Tk,3 é a árvore k-ária completa com 3 níveis. (Mitchem 1989)
A Coloração harmônica foi proposta inicialmente por Harary e Planthold (1982). Ainda hoje, muito pouco se conhece sobre ela.
Ver também Coloração completa Rotulagem Harmônica
Ligações externas A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards
Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
Categoria:Coloração de grafos