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≔Graph 1: an undirected unweighted graph with 10 vertices and 15 edge(s)
C5≔Graph 2: an undirected unweighted 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
What kind of issue would you like to report? (Optional)