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 = irgendein 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 und zulässige Reihenfolge der Knoten, für die man so 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.)