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. El número cromática armoniosa χ H ( G ) de un grafo G es el número mínimo de colores necesarios para cualquier colorante armonioso de G .
Cada gráfico tiene una coloración armoniosa, ya que basta con asignar a cada vértice un color distinto; por tanto, χ H ( G ) ≤ | V ( G ) |. 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 -ary 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.
Ver también
enlaces externos
- Una bibliografía de coloraciones armoniosas y números acromáticos por 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 : 151-157. doi : 10.1016 / 0012-365X (89) 90207-0 .
