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

# On a Reduction of the Interval Coloring Problem to a Series of Bandwidth Coloring Problems

## 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$, an interval coloring of $G$ is a function $I$ that assigns an interval $I(i)$ of $\omega_i$ consecutive integers (called colors) to each vertex $i\in V$ so that $I(i)\cap I(j)=\emptyset$ for all edges $\{i,j\}\in E$. The interval coloring problem is to determine an interval coloring that uses as few colors as possible. Assuming that a strictly positive integer weight $\delta_{ij}$ is associated with each edge $\{i,j\}\in E$, a bandwidth coloring of $G$ is a function $c$ that assigns an integer (called a color) to each vertex $i\in V$ so that $|c(i)-c(j)|\geq \delta_{ij}$ for all edges $\{i,j\}\in E$. The bandwidth coloring problem is to determine a bandwidth coloring with minimum difference between the largest and the smallest colors used. We prove that an optimal solution of the interval coloring problem can be obtained by solving a series of bandwidth coloring problems. Computational experiments demonstrate that such a reduction can help to solve larger instances or to obtain better upper bounds on the optimal solution value of the interval coloring problem.

, 23 pages