On the use of some known methods for T-colorings of graphs

A generalization of the classical graph coloring model is studied in this paper. The problem of interest is a variant of the general T-coloring problem related in the literature. The vertices of a graph are required to be colored in such a way that the two colors assigned to two adjacent vertices i and j differ by at least tij, where tij is a fixed coefficient associated to the edge [i,j]. The goal is to minimize the length of the spectrum of colors used. The paper presents 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.