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 which with the vertices of a graph G may be colored is called the chromatic number, denoted chi(G).

A vertex coloring of a graph with k or fewer colors is known as a k-coloring. A graph having a k-coloring (and therefore chromatic number chi(G)<=k) is said to be a k-colorable graph, while a graph having chromatic number chi(G)=k 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.

See also

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, k-Coloring, Labeled Graph, Minimum Edge Coloring, Minimum Vertex Coloring

Explore with Wolfram|Alpha


Christofides, N. "An Algorithm for the Chromatic Number of a Graph." Computer J. 14, 38-39, 1971.Gould, R. (Ed.). Graph Theory. Menlo Park, CA: Benjamin-Cummings, 1988.Manvel, B. "Extremely Greedy Coloring Algorithms." In Graphs and Applications (Ed. F. Harary and J. Maybee). New York: Wiley, pp. 257-270, 1985.Matula D. W.; Marble, G.; and Isaacson, J. D. "Graph Coloring Algorithms." In Graph Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 109-122, 1972.Skiena, S. "Finding a Vertex Coloring." §5.5.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 214-215, 1990.Thomassen, C. "The Number of k-Colorings of a Graph on a Fixed Surface." Disc. Math. 306, 3145-3153, 2006.Wilf, H. "Backtrack: An O(1) Expected Time Algorithm for the Graph Coloring Problem." Info. Proc. Let. 18, 119-121, 1984.

Referenced on Wolfram|Alpha

Vertex Coloring

Cite this as:

Weisstein, Eric W. "Vertex Coloring." From MathWorld--A Wolfram Web Resource.

Subject classifications