A Branch and Cut to Harmonious Coloring

For a graph G = (V, E), a k-coloring c is a function that assigns a color to every vertex of G using at most k distinct colors. A coloring is proper if there are no two neighbors with the same color. A coloring c is harmonious if c is proper and, for every distinct edges uv, xy ∈ E(G), {c(u), c(v)} ̸= {c(x), c(y)}. The harmonious chromatic number of G, denoted as h(G), is the minimum positive integer k such that there is a harmonious k-coloring of G. In this work, we present an integer-linear programming formulation to the problem and propose a user cut, alongside with the results of the tests of the approach over random-generated graphs.