IsVertexColorable - Maple Help

GraphTheory

 IsVertexColorable
 test if graph is vertex-colorable with k colors

 Calling Sequence IsVertexColorable(G, k, col) IsVertexColorable(G, k, d, col)

Parameters

 G - undirected graph k - non-negative integer (the number of colors) d - (optional) positive integer (distance) col - (optional) name

Description

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

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $P≔\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (1)
 > $\mathrm{IsVertexColorable}\left(P,2\right)$
 ${\mathrm{false}}$ (2)
 > $\mathrm{IsVertexColorable}\left(P,3,'\mathrm{col}'\right)$
 ${\mathrm{true}}$ (3)
 > $\mathrm{col}$
 $\left[\left[{2}{,}{5}{,}{7}{,}{10}\right]{,}\left[{4}{,}{6}{,}{9}\right]{,}\left[{1}{,}{3}{,}{8}\right]\right]$ (4)
 > $\mathrm{J7}≔\mathrm{FlowerSnark}\left(7\right):$
 > $\mathrm{IsVertexColorable}\left(\mathrm{J7},7,3,'\mathrm{col}'\right)$
 ${\mathrm{true}}$ (5)
 > $\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]$ (6)
 > $\mathrm{IsVertexColorable}\left(\mathrm{J7},9,4\right)$
 ${\mathrm{false}}$ (7)