Coloración de vértices donde no hay dos nodos vinculados que tengan el mismo emparejamiento de colores
Coloración armoniosa del árbol 7-ario completo con 3 niveles utilizando 12 colores. El número cromático armonioso de este grafo es 12. Si se usan menos colores, aparecerá un par de colores en más de un par de vértices adyacentes. Además, según la fórmula de Mitchem, χ H (T 7,3 ) = ⌈(3/2)(7+1)⌉ = 12 .
En teoría de grafos , una coloración armoniosa es una coloración de vértices (adecuada) en la que cada par de colores aparece como máximo en un par de vértices adyacentes . Es lo opuesto a la coloración completa , que en cambio requiere que cada par de colores ocurra al menos una vez. El número cromático armonioso χ H ( G ) de un grafo G es el número mínimo de colores necesarios para cualquier coloración armoniosa de G .
Todo grafo tiene una coloración armoniosa, pues basta con asignar a cada vértice un color distinto; así χ H ( G ) ≤ | V( G ) | . Existen trivialmente grafos G con χ H ( G ) > χ( G ) (donde χ es el número cromático ); un ejemplo es cualquier camino de longitud > 2 , que puede ser bicolor pero no tiene una coloración armoniosa con 2 colores.
