test if graph is vertex-colorable with k colors
IsVertexColorable(G, k, col)
IsVertexColorable(G, k, d, col)
non-negative integer (the number of colors)
(optional) positive integer (distance)
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.
P ≔ PetersenGraph⁡
P≔Graph 1: an undirected graph with 10 vertices and 15 edge(s)
J7 ≔ FlowerSnark⁡7:
Download Help Document