"A heuristic for the minimum cost chromatic partition problem"
Celso Ribeiro and Philippe dos Santos

The minimum cost chromatic partition problem is a variant of the graph coloring problem in which there are costs associated with the colors and we seek a vertex coloring minimizing the sum of the costs of the colors used in each vertex. It finds applications in VLSI design and some scheduling problems modeled on interval graphs. We propose a trajectory search heuristic using local search, path-relinking, perturbations, and restarts for solving the problem and discuss numerical results.