JCOL: A Java package for solving the graph coloring problem

04/24/2020

∙

by   , et al.

∙

0

∙

share

The graph coloring problem aims at assigning colors to the nodes of a graph such that no two connected nodes have the same color. The graph coloring problem is NP-complete and one of the harder problems to solve. Here we present a heuristic to solve this problem using three cascaded algorithms. The graph coloring problem was one of Karp’s 21 NP-complete problems, and is also know as the problem of finding the chromatic number of a graph. Several other problems reduce to graph coloring including solving generalized Sudoku puzzles.