Coloración de vértices donde no hay dos nodos vinculados que tengan el mismo par de colores
Coloración armoniosa del árbol completo de 7 arios con 3 niveles usando 12 colores. El número cromático armonioso de este gráfico es 12. Cualquier cantidad menor de colores dará como resultado que un par de colores aparezca 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értice (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 requiere que cada combinación de colores ocurra al menos una vez. El número cromático armonioso χ H ( G ) de un gráfico G es el número mínimo de colores necesarios para cualquier coloración armoniosa de G .
Cada gráfico tiene una coloración armoniosa, ya que basta asignar a cada vértice un color distinto; por lo tanto χ H ( GRAMO ) ≤ | V( GRAMO ) | . Existen trivialmente gráficos G con χ H ( G ) > χ ( G ) (donde χ es el número cromático ); un ejemplo es cualquier camino de longitud > 2 , que puede ser de 2 colores pero no tiene una coloración armoniosa con 2 colores.
Algunas propiedades de χ H ( G ) :
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). Todavía se sabe muy poco al respecto.
Una bibliografía de colores armoniosos y números acromáticos de Keith Edwards
Referencias
Frank, O.; Harary, F.; Plantholt, M. (1982). "El número cromático que distingue las líneas de un gráfico". Ars Combin . 14 : 241–252.
Jensen, Tommy R.; Toft, Bjarne (1995). Problemas de coloración de gráficos . Nueva York: Wiley-Interscience. ISBN 0-471-02865-7 .
Mitchem, J. (1989). "Sobre el armonioso número cromático de un gráfico". Matemáticas discretas . 74 (1–2): 151–157. doi : 10.1016/0012-365X(89)90207-0 .
