find a minimal vertex clique cover for a graph
return the size of a minimal vertex clique cover for a graph
(optional) non-negative integer (the number of cliques)
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.
P ≔ PetersenGraph⁡
P≔Graph 1: an undirected graph with 10 vertices and 15 edge(s)
C5 ≔ CycleGraph⁡5
C5≔Graph 2: an undirected graph with 5 vertices and 5 edge(s)
The GraphTheory[CliqueCover] and GraphTheory[CliqueCoverNumber] commands were introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
Download Help Document