Das Problem die Knoten eines Graphen mit einer minimalen Anzahl von Farben so zu färben, da\3 keine durch eine Kante verbundenen Knoten dieselbe Farbe haben, ist bis heute nicht effizient lösbar. Für planare Graphen, d.h. Graphen die man ohne Kantenüberschneidungen in der Ebene zeichnen kann, ist jedoch bekannt, da\3 vier Farben in jedem Fall ausreichen. Der Beweis ist aber sehr kompliziert und der quadratische Algorithmus nicht praktikabel.
Einen planaren Graphen mit fünf Farben zu färben ist dagegen sehr effizient in Linearzeit möglich. Der Vortrag soll auf der Grundlage von [5] solche Verfahren vorstellen. Sie lassen sich grob in zwei Ansätze unterscheiden. Bei sequentiellen Algorithmen wird ein bestimmter Knoten ausgewählt und mit einer Transformation aus dem Graphen entfernt. Wesentlich für die lineare Laufzeit ist, da\3 diese Transformationen effizient durchführbar sind. Bei den sogenannten Batch-Processing-Algorithmen besteht der entscheidende Schritt darin, da\3 in jeder Phase ein konstanter Bruchteil der Knoten entfernt werden kann.
Grundlage für die jeweiligen Garantien bilden interessante kombinatorische Eigenschaften planaren Graphen, die in [6] noch etwas genauer betrachtet werden.