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. The most common type of vertex coloring seeks to minimize the number of colors for a given graph. Such a coloring is known as a minimum vertex coloring, and the minimum number of colors with which the vertices of a graph may be colored is called the chromatic number, denoted .

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

In this sense, a vertex coloring is a proper coloring. A graph whose vertices are assigned arbitrary colors or labels, without requiring adjacent vertices to have distinct colors, is instead a vertex-colored graph.

A vertex coloring of a graph with or fewer colors is known as a k-coloring. A graph having a -coloring (and therefore chromatic number ) is said to be a k-colorable graph, while a graph having chromatic number is called a k-chromatic graph. The only one-colorable (and therefore one-chromatic) graphs are empty graphs, and two-colorable graphs are exactly the bipartite graphs. The four-color theorem establishes that all planar graphs are 4-colorable.