Perfekter Graph

In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der Knoten und allen inzidenten Kanten.

perfekter Graph

Beispiele:
Chordale Graphen Bipartite Graphen Vollständige Graphen Co-Graphen Vergleichbarkeitsgraphen

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.