Wieviele Farben benötigt man höchstens, um die Länder auf einer Landkarte so zu färben, dass benachbarte Länder verschiedene Farben haben? Dass man dabei mit erstaunlicherweise 4 Farben auskommt, wurde 1976 von Appel und Haken durch den ersten computergestützten Beweis gezeigt. Wir können diesen in der kurzen Veranstaltung zwar nicht wiedergeben, stattdessen zeigen wir aber die Aussage für 6 Farben -- über einen kleinen Exkurs in die Graphentheorie und ein trickreiches Argument. Unser Beweis liefert auch gleich einen einfachen Algorithmus, mit dem solche Färbungen effizient (mit dem Computer) gefunden werden können.

 

Ort:

Hochhaus, 7. Stock, R. 715

Ansprechpartner:

Prof. Dr. Anand Srivastav

Arbeitsgruppe: Diskrete Optimierung