TOPICS
Search

Minimum Vertex Coloring


VertexColoring

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 chi(G), and a graph with chromatic number chi(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 (Christofides 1971; Wilf 1984; Skiena 1990, p. 214), though more sophisticated methods can be substantially faster.

Computation of a minimum vertex coloring of a graph using heuristic methods is implemented in the Wolfram Language as FindVertexColoring[g].

Mehrotra and Trick (1996) devised a column generation algorithm for computing chromatic numbers and vertex colorings which solves most small to moderate-sized graph quickly.


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

Explore with Wolfram|Alpha

References

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.Mehrotra, A. and Trick, M. A. "A Column Generation Approach for Graph Coloring." INFORMS J. on Computing 8, 344-354, 1996.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, 2003.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.Wilf, H. "Backtrack: An O(1) Expected Time Algorithm for the Graph Coloring Problem." Info. Proc. Let. 18, 119-121, 1984.

Cite this as:

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

Subject classifications