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.