JCOL: A Java package for solving the graph coloring problem

Implementation of graph coloring heuristics like DSATUR, Iterated Greedy and Local Search. Also includes an implementation of the backtracking graph coloring algorithm.

Heuristic for Graph Coloring

Implementation of the DSatur heuristics for graph coloring in Java. The heuristic follows the following steps:

Compute a clique (maximum is good)
Color the clique
Sort the rest of the vertices in non-increasing order of the degree of saturation
Color the vertices in the order given by 3. Also, when a vertex is colored, change the degree of saturation of the neighboring vertices so that the order of coloring changes
Improve the coloring using Iterated Greedy techniques [2]
Improve the coloring using min-conflicts local search
Report the coloring