En la teoría de grafos, una coloración armónica es una coloración de vértice (adecuada) de modo que cualquier par de colores aparece en vértices adyacentes como máximo una vez. El número cromático armónico χ H ( G ) de un gráfico G es el número mínimo de colores necesarios para una coloración armónica del gráfico G .
Cualquier grafo tiene una coloración armónica, ya que basta con colorear cada vértice de un color diferente. Por lo tanto, χ H ( G ) ≤ |V(G)|. Es claro que hay grafos G con χ H ( G ) > χ( G ) (donde χ es un número cromático ). Un ejemplo sería un camino de longitud 2 cuyos vértices se pueden colorear con dos colores, pero no hay coloración armónica con 2 colores.
Algunas propiedades de χ H ( G ):
La coloración armónica fue propuesta por primera vez por Harary y Plantholt (1982). Poco se sabe sobre este tipo de coloración.