TOPICS

# Clique Covering Number

The clique covering number of a graph is the minimum number of cliques in needed to cover the vertex set of ., i.e., that form a vertex cover of . Since 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 is the chromatic number of a graph and is the graph complement of .

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

 graph complete -partite graph with complete graph 1 cycle graph

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

## Explore with Wolfram|Alpha

More things to try:

## 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