Algorithmen zur Färbung

Das Entscheidungsproblem COL

• Eingabe: (G, k)
• Frage: existiert konfliktfreie Färbung f für G mit | imgf|≤k

...ist NP-vollständig

⇒ kein effizienter Algorithmus bekannt

Näherungsverfahren (für Farben {1, 2,…}):

• färbe der Reihe nach jeden Punkt mit der kleinsten freien Farbe (= die nicht unter seinen Nachbarn vorkommt)

Heuristik für gute Reihenfolge?