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 minimizes 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 minimum coloring can be done using brute-force search (Christofides 1971; Wilf 1984; Skiena 1990, p. 214), though more sophisticated methods can be substantially faster.

The Wolfram Language function FindVertexColoring[g] is documented to find a coloring with a minimum number of colors.

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.

The number of minimum vertex colorings is given by , where is the chromatic polynomial of a graph and is its chromatic number.