Harmonious Coloring - Araújo, Júlio C. S.; Martins, Ana Beatriz da S.; Santos, Marcio C. (Proceedings of the Theory of Computation Meeting (ETC), 2022)
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 λ (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.