Graph
coloring is a famous problem from graph theory that has several important applications. We try to determine the number
of colors needed to color the vertices of a given graph G so that no two adjacent vertices have the same color. The
coloring problem is to find the fewest different colors,
k among all possible colorings. Such
k is said the chromatic number of G and is denoted by χ(G). Since graph coloring is NP-complete, various heuristic approaches are used to approximate the optimum solution such as local search, tabu method, simulated annealing, and hybrid algorithms. During the recent years, few exact (exponential-time)
methods have been proposed to solve this problem. In this paper we make a survey of exact methods for graph coloring problems, and we investigate the main differences between all these techniques.