Minimum 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. A vertex coloring that minimize the number of colors needed for a given graph  is known as a minimum vertex coloring of . The minimum number of colors itself is called the chromatic number, denoted , and a graph with chromatic number  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 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.

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  Expected Time Algorithm for the Graph Coloring Problem." Info. Proc. Let. 18, 119-121, 1984.