CliqueCover - Maple Help

GraphTheory

 CliqueCover
 find a minimal vertex clique cover for a graph
 CliqueCoverNumber
 return the size of a minimal vertex clique cover for a graph

 Calling Sequence CliqueCover(G) CliqueCover(G, k) CliqueCoverNumber(G)

Parameters

 G - undirected graph k - (optional) non-negative integer (the number of cliques)

Description

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

Definitions

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

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{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]$ (2)
 > $\mathrm{C5}≔\mathrm{CycleGraph}\left(5\right)$
 ${\mathrm{C5}}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 5 vertices and 5 edge\left(s\right)}}$ (3)
 > $\mathrm{CliqueCoverNumber}\left(\mathrm{C5}\right)$
 ${3}$ (4)
 > $\mathrm{CliqueCover}\left(\mathrm{C5}\right)$
 $\left[\left[{4}{,}{5}\right]{,}\left[{2}{,}{3}\right]{,}\left[{1}\right]\right]$ (5)

Compatibility

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