Vertex Coloring Problem

The vertex coloring problem is the optimization problem of finding a vertex coloring of a graph that uses as few colors as possible (Malaguti and Toth 2010). An optimal solution is a minimum vertex coloring, and the optimum value is the chromatic number .

The associated decision version takes a graph and a positive integer and asks whether has a vertex coloring using at most colors, equivalently whether . This decision problem is an NP-complete problem even when (Garey et al. 1976). Consequently, the optimization problem is an NP-hard problem.

In the words of Harary (1994, p. 127), "no convenient method is known for determining the chromatic number of an arbitrary graph." Exact solutions can be obtained by exhaustive search (Christofides 1971; Wilf 1984; Skiena 1990, p. 214), while Brelaz's heuristic algorithm can find a good, but not necessarily minimum, vertex coloring. Mehrotra and Trick (1996) devised a column generation algorithm for computing chromatic numbers and vertex colorings which solves most small to moderate-sized graphs quickly. Other algorithms for graph coloring are described by Matula et al. (1972) and Manvel (1985).