A k-coloring of a graph G is a vertex coloring that is an assignment of one of k possible colors to each vertex of G (i.e., a vertex coloring) such that no two adjacent vertices receive the same color.

Note that a k-coloring may contain fewer than k colors for k>2.

A k-coloring of a graph can be computed using MinimumVertexColoring[g, k] in the Wolfram Language package Combinatorica` , and all k-colorings may be computed using MinimumVertexColoring[g, k, All] (where, however, the command returns colorings that differ by permutation of colors only a single time).

The number of distinct k-colorings (where permutations of colors are counted separately) of a graph G is given by pi_G(k), where pi_G(x) is the chromatic polynomial of G.

See also

Chromatic Number, Chromatic Polynomial, Coloring, Edge Coloring, k-Chromatic Graph, k-Colorable Graph, Vertex Coloring

Explore with Wolfram|Alpha


Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 13, 1986.Thomassen, C. "The Number of k-Colorings of a Graph on a Fixed Surface." Disc. Math. 306, 3145-3153, 2006.

Referenced on Wolfram|Alpha


Cite this as:

Weisstein, Eric W. "k-Coloring." From MathWorld--A Wolfram Web Resource.

Subject classifications