Coloração harmônica
# Coloração harmônica

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):
A Coloração harmônica foi proposta inicialmente por Harary e Planthold (1982). Ainda hoje, muito pouco se conhece sobre ela.