k-着色

图 的 -着色是一种顶点着色，它将 种可能的颜色之一分配给 的每个顶点（即，一种顶点着色），使得没有两个相邻的顶点获得相同的颜色。

请注意，当 时，-着色可能包含少于 种颜色。

可以使用以下方法计算图的 -着色MinimumVertexColoringWolfram 语言包中的 [g, k]Combinatorica`，并且可以使用以下方法计算所有 -着色MinimumVertexColoring[g, k,All]（但是，该命令仅返回颜色排列不同的着色一次）。

图 的不同 -着色（其中颜色排列分别计数）的数量由 给出，其中 是 的色多项式。