Knoten-Färbung und Chromatische Zahl

Die Knotenfärbung ist eine Partitionierung der Knotenmenge eines Graphen in disjunkte, unabhängige Teilmengen, bei der direkt benachbarte Knoten keine identischen Marker erhalten dürfen.

• $k$-Färbung: Eine zulässige Abbildung $c:V(G)\to \{1,\dots ,k\}$, sodass für alle Kanten $\{u,v\}\in E(G)$ gilt:$$c(u)\ne c(v)$$
• Chromatische Zahl $\chi (G)$: Die minimale Anzahl $k$ an Farben, für die eine gültige $k$-Färbung des Graphen $G$ existiert.
• Klassenspezifische Schranken:
  • Vollständiger Graph: $\chi (K_n)=n$.
  • Bipartiter Graph: $\chi (G)=2$.
  • Planarer Graph (Vier-Farben-Satz): Für jeden planaren Graphen gilt garantiert $\chi (G)\le 4$.
• Komplexität: Das Entscheiden, ob ein Graph $k$-färbbar ist, ist für alle $k\ge 3$ ein NP-vollständiges Problem (gilt auch eingeschränkt für die Klasse der planaren Graphen).

Links

• DS_vollständiger_foliensatz.pdf