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