The clique covering number θ(G) of a graph G is the minimum number of cliques in G needed to cover the vertex set of G. Since θ(G) 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 θ(G) = χ(G^_), where χ(H) is the chromatic number of a graph H and G^_ is the graph complement of G.

chromatic number | clique covering | graph complement | maximum clique