On the use of some known methods forT-colorings of graphs

A generalization of the classical graph coloring model is studied in this paper. The problem we are interested in is a variant of the generalT-coloring problem related in the literature. We want to color the vertices of a graph in such a way that the two colors assigned to two adjacent verticesi andj differ by at least_ij, wheret_ij is a fixed coefficient associated to the edge [i, j]. The goal is to minimize the length of the spectrum of colors used. We present here the results produced by well-known heuristics (tabu search and simulated annealing) applied to the considered problem. The results are compared with optimal colorings obtained by a branch-and-bound algorithm.