A GRASP for Coloring Sparse Graphs
COAP
Manuel Laguna and Rafael Marti
------------------------------------------------------

Name and Address of Corresponding Author:

Manuel Laguna
Graduate School of Business,
University of Colorado,
Boulder, CO 80309-0419
USA

Phone number: (303) 492-6368

Fax number: (303) 492-5962

Email address: manuel.laguna@colorado.edu

Web site: http://bus.colorado.edu/faculty/laguna

ABSTRACT:
We first present a literature review of heuristics and 
metaheuristics developed for the problem of coloring graphs. 
We then present a Greedy Randomized Adaptive Search Procedure 
(GRASP) for coloring sparse graphs. The procedure 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 classical heuristics and implementations 
of simulated annealing and tabu search. 
GRASP is also found to be competitive with a genetic algorithm 
that is considered one of the best currently available for 
graph coloring.

Keywords: graph coloring, metaheuristics, GRASP