Minimum Vertex Coloring

A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. A vertex coloring that minimize the number of colors needed for a given graph is known as a minimum vertex coloring of . The minimum number of colors itself is called the chromatic number, denoted , and a graph with chromatic number is said to be a k-chromatic graph.

Brelaz's heuristic algorithm can be used to find a good, but not necessarily minimum vertex coloring. Finding a minimal coloring can be done using brute-force search (Christofides 1971; Wilf 1984; Skiena 1990, p. 214), though more sophisticated methods can be substantially faster.

Computation of a minimum vertex coloring of a graph using heuristic methods is implemented in the Wolfram Language as FindVertexColoring[g].

Mehrotra and Trick (1996) devised a column generation algorithm for computing chromatic numbers and vertex colorings which solves most small to moderate-sized graph quickly.