  The Equitable Coloring Problem is a variant of the Graph Coloring Problem
where the sizes of two arbitrary color classes differ in at most one unit. This
additional condition, called equity constraints, arises naturally in several
applications. Due to the hardness of the problem, current exact algorithms can
not solve large-sized instances. Such instances must be addressed only via
heuristic methods. In this paper we present a tabu search heuristic for the
Equitable Coloring Problem. This algorithm is an adaptation of the dynamic
TabuCol version of Galinier and Hao. In order to satisfy equity constraints,
new local search criteria are given. Computational experiments are carried out
in order to find the best combination of parameters involved in the dynamic
tenure of the heuristic. Finally, we show the good performance of our heuristic
over known benchmark instances.
