Saltar para o conteúdo

Coloração harmônica

Origem: Wikipédia, a enciclopédia livre.
Coloração harmônica de uma 7-árvore com 3 níveis usando 12 cores. O numero harmônico cromático desse grafo é 12 já que são 57 vértices, e o pareamento de cores é ncor*(ncor-1)/2 >= 57 sse ncor>=12. Além disso (3/2)*(7+1)=12(veja a fórmula de Mitchem).

Em teoria dos grafos, uma coloração harmônica é uma coloração de vértices (própria) na qual todo emparelhamento de cores aparece em no máximo um par de vértices adjacentes. O Numero harmônico cromático χH(G) de um grafo G é o número mínimo de cores necessárias para qualquer coloração harmônica de G.

Cada grafo tem uma coloração harmônica, visto que é suficiente atribuír a cada vértica uma cor distinta; então χH(G) ≤ |V(G)|. Existem trivialmente grafos G com χH(G) > χ(G) (onde χ é o número cromático); um exemplo é um caminho de tamanho 2, o qual pode ser 2-colorado(colorido com 2 cores) mas não tem uma coloração harmônica com 2 cores.

Algumas propriedades de χH(G):

  1. χH(Tk,3) = ⌈(3/2)(k+1)⌉, onde Tk,3 é a árvore k-ária completa com 3 níveis. (Mitchem 1989)

A Coloração harmônica foi proposta inicialmente por Harary e Planthold (1982). Ainda hoje, muito pouco se conhece sobre ela.


Ligações externas

[editar | editar código-fonte]

Referências

  • Frank, O.; Harary, F.; Plantholt, M. (1982). «The line-distinguishing chromatic number of a graph». Ars Combin. 14: 241–252 
  • Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
  • Mitchem, J. (1989). «On the harmonious chromatic number of a graph». Discrete Math. 74: 151–157. doi:10.1016/0012-365X(89)90207-0