There are many works regarding Graph Coloring Problem in the literature. Some tackle the general k-Coloring Problem while others consider variations of this problem such as Total Graph Coloring, Edge Coloring etc.

Here we consider only the researches for the k-Coloring Problem:

Joseph Culberson published some papers on the nineties where he analyzes some of the common algorithms to tackle this problem.
In his webpage, he has available the implementation of many algorithms that have been used to support other researches:
  • Greedy: Culberson implemented many variations of this algorithm as below:
    • Simple Greedy
    • Largest First Greedy
    • Smallest First Greedy
    • Random Sequence Greedy
    • Reverse Order Greedy
    • Stir Color Greedy
  • DSATUR
  • MAXIS
  • Backtrack DSATUR
  • Iterated Greedy
  • TABU

Last edited Jul 28, 2014 at 10:35 PM by lucasdeandrade87, version 1