Vertex Coloring

A vertex coloring is an assignment of labels or colors to the vertices of a graph such that the endpoints of every edge receive different colors. 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 . Finding a minimum vertex coloring is the vertex coloring problem.

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 k-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.