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  may be colored is called the chromatic number, denoted .

A minimum vertex coloring can be computed using MinimumVertexColoring[g] in the Wolfram Language package Combinatorica` . Brelaz's heuristic algorithm can be used to find a good, but not necessarily minimal, vertex coloring of a graph. It is implemented as BrelazColoring[g] in the Wolfram Language package Combinatorica` .

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

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.S

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