The CliqueCover(G) command returns a minimum vertex clique cover for the graph G.

The CliqueCover(G,k) command attempts to produce a clique cover for G of no more than k cliques. If such a partition is possible, a list of cliques is returned. If not possible, an error message is displayed.

The CliqueCoverNumber(G) command returns the size of a minimum vertex clique cover for G. Note this equivalent to computing the chromatic number for the graph complement of G.

The problem of finding a clique cover of size k for a graph is NP-complete, meaning that no polynomial-time algorithm is presently known. The exhaustive search will take an exponential time on some graphs.

A clique cover or vertex clique cover of a graph G is a partition of the vertices of G into cliques. That is, it is a set of mutually disjoint subsets of the vertices of G, each of which is a clique. Each clique cover is a coloring of the graph complement of G.

A minimum clique cover of a graph G is a clique cover of minimum size for the graph G.

The clique cover number of a graph G is the cardinality of a minimum clique cover of G. It is equal to the chromatic number of the graph complement of G.

$\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{CliqueCover}\left(P\right)$

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

$\mathrm{C5}≔\mathrm{CycleGraph}\left(5\right)$

$\mathrm{C5}≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 5\; vertices\; and\; 5\; edge(s)}$

$\mathrm{CliqueCoverNumber}\left(\mathrm{C5}\right)$

$3$

$\mathrm{CliqueCover}\left(\mathrm{C5}\right)$

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

The GraphTheory[CliqueCover] and GraphTheory[CliqueCoverNumber] commands were introduced in Maple 2016.

For more information on Maple 2016 changes, see Updates in Maple 2016.