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 |