About equivalent interval colorings of weighted graphs

Given a graph G=(V,E)G=(V,E) with strictly positive integer weights ωiωi on the vertices i∈Vi∈V, a kk-interval coloring of GG is a function II that assigns an interval I(i)⊆{1,…,k}I(i)⊆{1,…,k} of ωiωi consecutive integers (called colors) to each vertex i∈Vi∈V. If two adjacent vertices xx and yy have common colors, i.e. I(i)∩I(j)≠0̸I(i)∩I(j)≠0̸ for an edge [i,j][i,j] in GG, then the edge [i,j][i,j] is said conflicting  . A kk-interval coloring without conflicting edges is said legal  . The interval coloring problem (ICP) is to determine the smallest integer kk, called interval chromatic number   of GG and denoted χint(G)χint(G), such that there exists a legal kk-interval coloring of GG. For a fixed integer kk, the kk-interval graph coloring problem (kk-ICP) is to determine a kk-interval coloring of GG with a minimum number of conflicting edges. The ICP and kk-ICP generalize classical vertex coloring problems   where a single color has to be assigned to each vertex (i.e., ωi=1ωi=1 for all vertices i∈Vi∈V).Two kk-interval colorings I1I1 and I2I2 are said equivalent   if there is a permutation ππ of the integers 1,…,k1,…,k such that ℓ∈I1(i)ℓ∈I1(i) if and only if π(ℓ)∈I2(i)π(ℓ)∈I2(i) for all vertices i∈Vi∈V. As for classical vertex coloring, the efficiency of algorithms that solve the ICP or the kk-ICP can be increased by avoiding considering equivalent kk-interval colorings, assuming that they can be identified very quickly. To this purpose, we define and prove a necessary and sufficient condition for the equivalence of two kk-interval colorings. We then show how a simple tabu search algorithm for the kk-ICP can possibly be improved by forbidding the visit of equivalent solutions.