Graphenfärbungen

Das bekannteste Problem auf diesem Gebiet ist wohl das "Vierfarbenproblem": Kann man jede beliebige Landkarte mit vier verschiedenen Farben färben? Dabei gelten folgende Regeln für das Färben: keine zwei Länder, die in mehr als einem Punkt aneinander grenzen, dürfen die gleiche Farbe bekommen. Ausserdem sind Exklaven ausgeschlossen. Die Vermutung, dass vier Farben zum Färben genügen, stellte Francis Guthrie schon 1852 auf, als er die Karte von England färben wollte. In den nächsten vierzig Jahren folgten fehlerhafte Beweisversuche dieser Vermutung, aber auch der Beweis, dass fünf Farben reichen. Erst 1976 gelang es Kenneth Appel und Wolfgang Haken den Vierfarbensatz zu beweisen. Allerdings auch nur mit massivem Rechnereinsatz.
Färbungen sind ein Thema, an dem gut die nichtalgorithmischen Kompetenzen erworben werden können, die im Rahmenplan aufgezält werden. (Modellieren mit Graphen, Graphen als Realsituation interpretieren, Grapheneigenschaften entdecken und beweisen.)