Graph Coloring Program -- Sepp Hartung and Rolf Niedermeier

GraphColoring is a free Java program that provides several solvers for the graph coloring problem. The implementation is described in:

Sepp Hartung and Rolf Niedermeier
"Incremental List Coloring of Graphs, Parameterized by Conservation"

The program is distributed under the terms of the GNU General Public License (GPL). It is written in Java and requires a Java Virtual Machine which is compatible to version 1.5. It can be invoked by

java -jar GraphColoring.jar FILENAME SOLVER

The file FILENAME must contain the graph description in the DIMACS standard ASCII format. The parameter SOLVER determines which graph coloring algorithm is used. The algorithms currently available are

1 simple Greedy Algorithm
2 Iterated Greedy Algorithm
3 Search Tree based Algorithm

The Iterated Greedy Algorithm was introduced by J. Culberson and F. Luo in "Exploring the k-colorable landscape with iterated greedy" (1996).

The program outputs the coloring to the standard output.