Harmonious Coloring

• Júlio C. S. Araújo UFC
• Ana Beatriz da S. Martins UFC
• Marcio C. Santos UFC

DOI: https://doi.org/10.5753/etc.2022.223216

Abstract

A k-coloring c: V(G)->{1, 2, ..., k} is a line-distinguishing coloring if each pair of distinct edges have different sets of colors in their endpoints. The line-distinguishing chromatic number of G is \lambda (G)=min{k\in\mathbb{N}: G admits a line distinguishing k-coloring}. If a line-distinguishing coloring c is proper, then c is an harmonious coloring. The harmonious chromatic number, denoted by h(G), is the minimum k\in\mathbb{N} such that G has a harmonious k-coloring. In this paper, we first present a sufficient and necessary condition for h(G) to be k, for any graph G and k\in\mathbb{N}. Then, we present Integer- Programming formulations to compute h(G) and some preliminary tests on random graphs with distinct edge densities.

Keywords: Graphs, Coloring, Integer-Programming, Harmonious Coloring

References

Campêlo, M., Campos, V. A., and Corrêa, R. C. (2008). On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics, 156(7):1097–1111. GRACO 2005.

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.