Graph/Färbung/Einfache Eigenschaften/Fakt

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Für die chromatische Zahl eines Graphen gelten die folgenden Aussagen.

  1. Ein Graph ist genau dann nicht leer, wenn seine chromatische Zahl ist.
  2. Ein nichtleerer Graph besitzt genau dann die chromatische Zahl , wenn er keine Kanten besitzt.
  3. Ein Graph ist genau dann bipartit, wenn seine chromatische Zahl ist.
  4. Es ist
  5. Der vollständige Graph besitzt die chromatische Zahl .