k-Coloring
A 
-coloring of a graph 
is a vertex coloring that is an assignment of one of 
possible colors to each vertex of 
(i.e., a vertex coloring) such that no two adjacent vertices receive the same color.
Note that a 
-coloring may contain fewer than 
colors for 
.
A 
-coloring of a graph can be computed using MinimumVertexColoring[g, k] in the Wolfram Language package Combinatorica` , and all 
-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 
-colorings (where permutations of colors are counted separately) of a graph 
is given by 
, where 
is the chromatic polynomial of 
.
REFERENCES
Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 13, 1986.
