Colores armoniosos

En teoría de grafos , una coloración armónica es una coloración de vértices (propia) 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 requiere que cada par de colores aparezca al menos una vez. El número cromático armónico χ _H ( G ) de un grafo G es el número mínimo de colores necesarios para cualquier coloración armónica de G.

Cada grafo tiene una coloración armoniosa, ya que basta con asignar a cada vértice un color distinto; por lo tanto, χ _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 2-coloreado pero no tiene una coloración armoniosa con 2 colores.

Algunas propiedades de χ _H ( G ) :

${\displaystyle \chi _{H}(T_{k,3})=\left\lceil {\frac {3(k+1)}{2}}\right\rceil ,}$

donde T _{k ,3} es el árbol k -ario completo con 3 niveles. (Mitchem 1989)

La coloración armoniosa fue propuesta por primera vez por Harary y Plantholt (1982). Sin embargo, aún se sabe muy poco al respecto.

• Coloración completa
• Etiquetado armonioso

• Bibliografía sobre colores armoniosos y números acromáticos, por Keith Edwards.

• Frank, O.; Harary, F.; Plantholt, M. (1982). "El número cromático que distingue líneas de un grafo". Ars Combin . 14 : 241–252 .
• Jensen, Tommy R.; Toft, Bjarne (1995). Problemas de coloración de grafos . Nueva York: Wiley-Interscience. ISBN 0-471-02865-7.
• Mitchem, J. (1989). "Sobre el número cromático armónico de un grafo" . Discrete Math . 74 ( 1–2 ): 151–157 . doi : 10.1016/0012-365X(89)90207-0 .