eine Menge {H₁,H₂, …, H_q} von Cliquen aus einem Graphen G, die alle Ecken des Graphen enthalten, für die also

\begin{eqnarray}E(G)=E({H}_{1})\cup E({H}_{2})\cup \ldots \cup E({H}_{q})\end{eqnarray}

Die minimale Anzahl von Cliquen, mit der man G überdecken kann, heißt Cliquenüberdeckungszahl oder Cliquenpartitionszahl, und wird mit Θ(G) bezeichnet.

Ist \(\bar{G}\) der Komplementärgraph von G und sind α(G) die Unabhängigkeitszahl, χ(G) die chromatische Zahl und ω(G) die Cliquenzahl, so bestehen die leicht einzusehenden Zusammenhänge

\begin{eqnarray}\begin{array}{c}\chi (G)\ge \omega (G),\Theta (G)\ge \alpha (G),\\ \omega (G)=\alpha (\bar{G}),\,\text{und}\,\Theta (G)=\chi (\bar{G}).\end{array}\end{eqnarray}

Ein Graph G wird perfekt genannt, wenn α(G′) = Θ(G′) für jeden induzierten Teilgraphen G′ von G gilt.