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 G is known as a minimum vertex coloring of G. The minimum number of colors itself is called the chromatic number, denoted χ(G), and a graph with chromatic number χ(G) = k 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, though more sophisticated methods can be substantially faster.

Brelaz's heuristic algorithm | Brooks' theorem | chromatic number | chromatic polynomial | coloring | edge chromatic number | edge coloring | four-color theorem | graph coloring | k-chromatic graph | k-colorable graph | labeled graph | minimum edge coloring | vertex coloring