Let G=(V, E) be an undirected graph, where V is a set of vertices and E is a set of edges, the graph coloring problem (GCP) is to partition V into K color classes, where each is a subset of V labeled with same color. For a proper coloring, each color class forms an independent set, which has no adjacent vertices. GCP is one of the most notorious models in graph theory. It also has various applications, such as timetabling, register allocation, etc.