while (nicht alle Knoten gefärbt) { x = irgendein nicht gefärbter Knoten; M = Menge der Farben der Nachbarn von x; x erhält kleinste Farbe, die nicht in M ist; }
Aufgabe:
Finde Beispiele (d. h. Graph mit Knotenreihenfolge), für die der Algorithmus keine optimale Färbung findet. Wie groß kann die Abweichung (= Anzahl der unnötig benutzten Farben) werden?