Coloração Harmoniosa
Resumo
Uma k-coloração c: V(G)->{1, 2, ..., k} é uma coloração linha-distinguível se cada par de arestas distintas tem conjuntos de cores distintos em suas extremidades. O número cromático linha-distinguível de G é \lambda (G)=min {k\in\mathbb{N}: G tem uma k-coloração linha-distinguível}. Se uma coloração linha-distinguível c é própria, então c é uma coloração harmoniosa. O número cromático harmonioso, denotado por h(G), é o menor k\in \mathbb{N} tal que G tem uma k-coloração harmoniosa. Neste trabalho, apresentamos uma condição necessária e suficiente para h(G) ser k, para um grafo arbitrário e k\in \mathbb{N}. Após isso, apresentamos formulações de programação inteira para computar h(G) e alguns testes preliminares em grafos aleatórios com densidades de arestas distintas.
Referências
de Oliveira, H. C. (2019). Coloração harmônica de grafos: uma abordagem usando programação inteira. Tese de conclusão de curso, Campus de Russas, Universidade Federal do Ceará, Russas.
Edwards, K. and McDiarmid, C. (1995). The complexity of harmonious colouring for trees. Discret. Appl. Math., 57(2-3):133–144.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, first edition edition.
Hopcroft, J. E. and Krishnamoorthy, M. S. (1983). On the harmonious coloring of graphs. SIAM. J. on Algebraic and Discrete Methods, pages 306-311.
Lee, S.-M. and Mitchem, J. (1987). An upper bound for the harmonious chromatic number of a graph. Journal of Graph Theory, 11(4):565–567.
Miller, Z. and Pritikin, D. (1991). The harmonious coloring number of a graph. Discrete Mathematics, 93:211–228.
West, D. B. (2001). Introduction to Graph Theory. Pearson Education.
