Greedy-Algorithmus zur Graphenfärbung

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;
}

• Algorithmus findet immer eine zulässige Färbung
• verbraucht $\le$$\Delta$(G) + 1 Farben

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?