Register-Graphen-Färbung (Heuristik)

Heuristik für Färbung von G:

• wenn | G| = 1, dann nimm erste Farbe
• wenn | G| > 1, dann
  • wähle x = Knoten mit minimalem Grad,
  • färbe G $\setminus$ {x}
  • gib x die kleinste Farbe, die nicht in Nachbarn G(x) vorkommt.

Aufgabe: finde Graphen G, für die man nach dieser Heuristik keine optimale Färbung erhält.

Falls dabei mehr Farben als Maschinenregister, dann lege die seltensten Registerfarben in Hauptspeicher.

(Es gibt bessere, aber kompliziertere Methoden.)