TOPICS
Search

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

 theta(G)=chi(G^_),

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

References

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. https://mathworld.wolfram.com/CliqueCoveringNumber.html

Subject classifications