Coloring large graphs based on independent set extraction We present an effective approach ({ssf EXTRACOL}) to coloring large graphs. The proposed approach uses a preprocessing method to extract large independent sets from the graph and a memetic algorithm to color the residual graph. Each preprocessing application identifies, with a dedicated tabu search algorithm, a number of pairwise disjoint independent sets of a given size in order to maximize the vertices removed from the graph. We evaluate {ssf EXTRACOL} on the 11 largest graphs (with 1000 to 4000 vertices) of the {ssf DIMACS} challenge benchmarks and show improved results for four very difficult graphs (DSJC1000.9, C2000.5, C2000.9, C4000.5). The behavior of the proposed algorithm is also analyzed.

This software is also peer reviewed by journal TOMS.