Forschungsinstitut für Diskrete Mathematik

Vorlesung "Graphenfärbungen"

Wintersemester 2006/07



Wie viele Farben benötigt man, um die Länder einer Landkarte so zu färben, daß keine zwei Nachbarländer die gleiche Farbe haben? Dieses klassische mathematische Problem, das bereits 1852 formuliert wurde und mehr als ein Jahrhundert ungelöst blieb, ist ein Spezialfall von Graphenfärbungsproblemem, die Thema dieser Vorlesung sind. Wir behandeln Knoten- und Kantenfärbungen von Graphen und untersuchen dabei sowohl algorithmische Aspekte (Härteresultate, Approximationsalgorithmen) als auch graphentheoretische Ergebnisse (z.B. Eigenschaften perfekter Graphen).


Vorkenntnisse: Grundstudium. Kenntnisse von elementaren Begriffen der Graphentheorie sind von Vorteil.
Ort: Gerhard-Konow-Hörsaal (im Arithmeum, Lennéstr. 2)
Zeit: Mittwochs 15-17 Uhr


U. Brenner