Groupe d’études et de recherche en analyse des décisions

About Equivalent Interval Colorings of Weighted Graphs

Mathieu Bouchard, Mirjana Cangalovic et Alain Hertz

Given a graph G=(V,E) with strictly positive integer weights $\omega_i$ on the vertices $i\in V$, a k-interval coloring of G is a function I that assigns an interval $I(i)\subseteq \{1,\cdots,k\}$ of $\omega_i$ consecutive integers (called colors) to each vertex $i\in V$. If two adjacent vertices x and y have common colors, i.e. $I(i)\cap I(j)\neq\emptyset$ for an edge $[i,j]$ in G, then the edge $[i,j]$ 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 $\chi_{int}(G)$, 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., $\omega_i=1$ for all vertices $i\in V$).

Two k-interval colorings I1 and I2 are said equivalent if there is a permutation $\pi$ of the integers $1,\cdots,k$ such that $\ell\in I_1(i)$ if and only if $\pi(\ell)\in I_2(i)$ for all vertices $i\in V$. 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.

, 18 pages