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 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.
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 Computing8, 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.