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 |