COSINE: A new graph coloring algorithm

COSINE is a graph coloring algorithm which has been especially designed for producing optimal colorings in a large class of perfect graphs. This algorithm is used as a heuristic method for getting an upper bound on the chromatic number of general graphs; this estimation is then considered as an initial step of a more sophisticated coloring procedure based on tabu search techniques. COSINE is compared with other methods having similar complexity and the paper shows that COSINE realizes a good compromise between computational time and performance level.