Lexikon der Mathematik: Cliquenüberdeckung
eine Menge {H1,H2, …, Hq} von Cliquen aus einem GraphenG, 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}
gilt.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.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.