Clique Covering Number

The clique covering number theta(G) of a graph G is the minimum number of cliques in G needed to cover the vertex set of G., i.e., that form a vertex cover of G. Since theta(G) involves the minimum number of cliques, only maximal cliques need be considered (since non-maximal cliques could not yield a clique cover of smaller size).

The clique covering number is also given by


where chi(H) is the chromatic number of a graph H and G^_ is the graph complement of G.

The clique covering number of some classes of graph are given by

graph Gtheta(G)
complete k-partite graph K_(n_1,...,n_k) with k>1max_(1<=i<=k)n_i
complete graph K_n1
cycle graph C_n{n/2   for n even; (n+1)/2   for n odd

See also

Chromatic Number, Clique Covering, Graph Complement, Intersection Number, Maximum Clique

Explore with Wolfram|Alpha


West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 226, 2000.

Cite this as:

Weisstein, Eric W. "Clique Covering Number." From MathWorld--A Wolfram Web Resource.

Subject classifications