A GRASP for coloring sparse graphs

We first present a literature review of heuristics and metaheuristics devel oped for the problem of coloring graphs. We then present a Greedy Randomize d Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedu re is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to clas sical heuristics and implementations of simulated annealing and tabu search . GRASP is also found to be competitive with a genetic algorithm that is co nsidered one of the best currently available for graph coloring.