Given a graph G=(V,E) with strictly positive integer weights on the vertices , a k-interval coloring of G is a function I that assigns an interval of consecutive integers (called colors) to each vertex . If two adjacent vertices x and y have common colors, i.e. for an edge in G, then the edge is said conflicting. A k-interval coloring without conflicting edges is said legal. The interval coloring problem (ICP) is to determine the smallest integer k, called interval chromatic number of G and denoted , such that there exists a legal k-interval coloring of G. For a fixed integer k, the k-interval graph coloring problem (k-ICP) is to determine a k-interval coloring of G with a minimum number of conflicting edges. The ICP and k-ICP generalize classical vertex coloring problems where a single color has to be assigned to each vertex (i.e., for all vertices ).

Two k-interval colorings I₁ and I₂ are said equivalent if there is a permutation of the integers such that if and only if for all vertices . As for classical vertex coloring, the efficiency of algorithms that solve the ICP or the k-ICP can be increased by avoiding considering equivalent k-interval colorings. To this purpose, we define and prove a necessary and sufficient condition for the equivalence of two k-interval colorings. We then show how a simple tabu search algorithm for the k-ICP can possibly be improved by forbidding the visit of equivalent solutions.