Direkt zum Inhalt

Lexikon der Mathematik: Cliquenüberdeckung

eine Menge {H1,H2, …, Hq} 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}

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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos