Heuristics for the robust coloring problem

let g and ？ be complementary graphs. given a penalty function defined on the edges of ？, we will say that the rigidity of a k-coloring of g is the sum of the penalties of the edges of ？ joining vertices of the same color. based on the previous definition, the robust coloring problem (rcp) is stated as the search of the minimum rigidity kcoloring. in this work a comparison of heuristics based on simulated annealing, grasp and scatter search is presented. these are the best results for the rcp that have been obtained.