EPCOT - AN EFFICIENT PROCEDURE FOR COLORING OPTIMALLY WITH TABU SEARCH

We present an exact procedure for coloring the nodes of a graph with as few colors as possible. The problem of deciding whether an arbitrary graph can be colored with k colors is NP-complete. The procedure is based on an implicit enumeration technique. At some stages of the algorithm heuristic methods are needed; here we will use the Tabu Search technique. The resulting coloring procedure is described. Computational experience is reported; it shows that random graphs with edge density 0.5 and having up to 70 nodes can be colored in an optimum way.