proper k-coloring

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

chromatic number | chromatic polynomial | coloring | edge coloring | k-chromatic graph | k-colorable graph | vertex coloring