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.