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 G theta(G)
complete k-partite graph K_(n_1,...,n_k) with k>1 max_(1<=i<=k)n_i
complete graph K_n 1
See also
Chromatic Number, Clique Covering, Graph Complement, Intersection Number, Maximum CliqueExplore with Wolfram|Alpha
WolframAlpha
More things to try:
References
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 226, 2000.Referenced on Wolfram|Alpha
Clique Covering NumberCite this as:
Weisstein, Eric W. "Clique Covering Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CliqueCoveringNumber.html