TOPICS
Search

Minimum Vertex Coloring

VertexColoring

A minimum vertex coloring of a graph G is a vertex coloring that uses the fewest possible colors. The task of finding one is the vertex coloring problem. The number of colors in a minimum vertex coloring is the chromatic number chi(G), and a graph with chromatic number chi(G)=k is said to be a k-chromatic graph.

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

The number of minimum vertex colorings is given by pi(chi), where pi(x) is the chromatic polynomial of a graph and chi is its chromatic number.

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

Explore with Wolfram|Alpha

References

Gould, R. (Ed.). Graph Theory. Menlo Park, CA: Benjamin-Cummings, 1988.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, 2003.Soifer, A. The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, 2024.Thomassen, C. "The Number of k-Colorings of a Graph on a Fixed Surface." Disc. Math. 306, 3145-3153, 2006.

Referenced on Wolfram|Alpha

Minimum Vertex Coloring

Cite this as:

Weisstein, Eric W. "Minimum Vertex Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MinimumVertexColoring.html

Subject classifications