Graphenparameter

• Maximalgrad Δ(G)
• chromatische Zahl χ(G)

  kleinstes k, für das G eine konfliktfreie k-Färbung besitzt

• Cliquenzahl ω(G): maximale Knotenzahl einer Clique

  (= vollständig verbundener Teilgraph)

Anwendungen:

• Folgerung aus Algorithmus: χ(G)≤Δ(G) + 1.

  Für welche Graphen gilt Gleichheit?

• größter Fehler des heuristischen Algorithmus?
• trivial ω(G)≤χ(G). Möglicher Abstand?