Graph coloring problem (GCP) is a popular NP-hard problem problem.

It consists of coloring the adjacent vertex (or edge) in a graph with minimum different number of colors. It is used to solve a variety of real-world problems, such as like map coloring, scheduling and timetabling.

The number of the least possible colors to be used in a graph is called chromatic number.

Various heuristic methods have been developed in order to solve the GCP. Here you will find the implementaion for Welsh and Powell method. The WP algorithm finds out the best solution (minimum chromatic number) in the shortest time [1].

[1] A Performance Comparison of Graph Coloring Algorithms.

Trimming Graphs Using Clausal Proof Optimization

DIMACS graph coloring instances. (2016)