Clique Covering Number

The clique covering number  of a graph  is the minimum number of cliques in  needed to cover the vertex set 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

REFERENCES

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