The IsVertexColorable(G,k) function returns true if the graph G is k-colorable and false otherwise. That is, if the vertices of G can be colored with k colors such that no two adjacent vertices have the same color.

If an optional argument d is specified, then IsVertexColorable(G,k,d) returns true if the graph G is (k,d) colorable, and false otherwise. That is, it returns true if the vertices of G can be colored with k colors such that two vertices with any given color are at least distance d apart.  When d is not specified it is assumed to be 1.

If a name col is specified, then this name is assigned the list of colors of a coloring of the vertices of G, if it exists.

The algorithm first tries a greedy coloring of the vertices of G starting with a maximum clique in G.  If this fails to find a k-coloring it does an exhaustive search using a backtracking algorithm.

The problem of testing if a graph is k-colorable is NP-complete, meaning that no polynomial-time algorithm is known. The exhaustive search will take exponential time on some graphs.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{SpecialGraphs}\right)\:$

$P≔\mathrm{PetersenGraph}\left(\right)$

$P≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edge(s)}$

$\mathrm{IsVertexColorable}\left(P\,2\right)$

$\mathrm{false}$

$\mathrm{IsVertexColorable}\left(P\,3\,'\mathrm{col}'\right)$

$\mathrm{true}$

$\mathrm{col}$

$\left[\left[2\,5\,7\,10\right]\,\left[4\,6\,9\right]\,\left[1\,3\,8\right]\right]$

$\mathrm{J7}≔\mathrm{FlowerSnark}\left(7\right)\:$

$\mathrm{IsVertexColorable}\left(\mathrm{J7}\,7\,3\,'\mathrm{col}'\right)$

$\mathrm{true}$

$\mathrm{col}$

$\left[0\,3\,6\,2\,5\,1\,4\,3\,0\,3\,0\,3\,6\,2\,6\,2\,5\,2\,5\,1\,5\,1\,4\,1\,4\,0\,4\,0\right]$

$\mathrm{IsVertexColorable}\left(\mathrm{J7}\,9\,4\right)$

$\mathrm{false}$