Coloração harmônica

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):

1. χ_H(T_k,3) = ⌈(3/2)(k+1)⌉, onde T_k,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

Referências

• Frank, O.; Harary, F.; Plantholt, M. (1982). «The line-distinguishing chromatic number of a graph». Ars Combin. 14: 241–252 
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
• Mitchem, J. (1989). «On the harmonious chromatic number of a graph». Discrete Math. 74: 151–157. doi:10.1016/0012-365X(89)90207-0