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 .