Seminar: Graphenfärbung (SS 2004)

	Seminar: Graphenfärbung
	Sommersemester 2004

LV-Nr.: 0230 L 318

Prof. Dr. Martin Grötschel und Dr. Frank Lutz

Inhalt

Das klassische Graphenfärbungsproblem besteht in der Aufgabe, bei einem gegebenen Graphen die Knoten so zu färben, dass je zwei benachbarte Knoten verschiedene Farben haben. Dies ist ein jahrhundertealtes Problem mit reicher Theorie, das in der Praxis immer noch nicht gut gelöst werden kann. Durch industrielle Fragestellungen hat sich die theoretische und algorithmische Analyse des Graphenfärbungsproblems inzwischen auf verschiedene Verallgemeinerungen und Varianten verlagert. Neben dem Kantenfärbungsproblem sind das T-Färbungs- und das Listenfärbungsproblem von besonderem Interesse. In diesem Seminar werden Abschnitte aus einigen Büchern zur Färbungstheorie und neuere Aufsätze zum Thema behandelt.

Voraussetzungen

Lineare Algebra, Graphen- und Netzwerkalgorithmen (ADM I), Lineare Optimierung (ADM II).

Hinweise zu den Vorträgen

Richtlinien für die Vortragsgestaltung und die Scheinvergabe:

Die wesentliche Leistung ist ein Vortrag von ca. 60 Minuten über das zugeteilte Thema. Im Vortrag sollen in verständlicher Form wichtige Ergebnisse des (für den Vortrag zentralen) Artikels vorgestellt werden. Ausgewählte Beweise sollen erklärt werden.
Die Vortragsform und -medien kann jeder frei wählen. Als Vortragsmedien stehen Tafel, Overhead-Projektor und Beamer zur Verfügung. Insbesondere bei Beamerbenutzung sollte die Technik vorher geprüft werden.
Zum Vortragstermin ist von den Vortragenden eine etwa 5-seitige Ausarbeitung zum Thema vorzulegen. Diese wird an alle Seminarteilnehmerinnen und Seminarteilnehmer verteilt. In dieser Ausarbeitung sollen wesentliche Definitionen und Ergebnisse zusammengefasst werden. Die Ausarbeitung soll in ``Publikationsqualität'' vorliegen. Es wird empfohlen, die Ausarbeitung mit Hilfe von LaTeX zu schreiben. Für LaTeX-Unkundige ist dies vielleicht ein guter Zeitpunkt, sich LaTeX anzueignen, da man im mathematischen Leben kaum darum herumkommt. (Empfehlenswerte Literatur für Einsteiger ist der erste Band der LaTeX-Serie von Helmut Kopka, erschienen bei Addison-Wesley. Bitte achten Sie darauf, dass es sich um eine ``aktuelle'' Version handelt, die LaTeX2e behandelt.)

Veranstaltungstermin

Das Seminar wird als Blockseminar am Wochenende 4.-6. Juni 2004 im Seminarraum 2006 des Konrad-Zuse-Zentrum durchgeführt (Lageplan).

Programm

Freitag, 04.06.2004

09:00	Stefan Heinz: Greedy-Färbung und Verwandtes
10:00	Raphael Traut: Kritische Graphen
11:00	Besichtigung des Höchstleistungsrechners IBM pSeries 690
11:45	Eduard Kolberg: Der Satz von Turan und Verallgemeinerungen
12:45	Mittagspause
13:45	Christina Ottmann: Die Probabilistische Methode
14:45	Benjamin Feldhahn: Färbung von Hypergraphen
15:45	Pause
16:00	Harald Schülzke: Perfekte Graphen
17:00	Jérôme Kunegis: Fraktionale Graphenfärbung

Samstag, 05.06.2004

09:00	Rüdiger Stephan: Das chromatische Polynom
10:00	Mikis Rolke: Kantenfärbung I
11:00	Pause
11:10	Dominik Piesker: Kantenfärbung II
12:10	Mittagspause
13:15	Nicole Vigh: Listenfärbung, T-Färbung
14:15	Fabian Stöffler: Online-Färbung
15:15	Pause
15:30	Leonid Korolev: Frequenzplanung
16:30	Bertold Bongardt: Heuristiken und Approximationsalgorithmen für das Graphenfärbungsproblem

Sonntag, 06.06.2004

09:00	Mike Schülken: Der 5-Farbensatz
10:00	Ferdinand Jurczek: Beweis des 4-Farbensatzes
11:00	Pause
11:10	Henry Irwan: Färben von Flächen
12:10	Mittagspause
13:15	Vili Dhamo: Die Kneser-Vermutung
14:15	Tim Januschowski: Topologische untere Schranken für die chromatische Zahl

Kontakte

	Sprechstunde	Raum	Telefon	email
Prof. Dr. Martin Grötschel	n.V.	MA 302	84185-210	groetschelzib.de
Dr. Frank Lutz	n.V.	MA 624	314-25 751	lutzmath.tu-berlin.de

$Valid HTML 4.0!$ Zuletzt aktualisiert: 7. Juni 2004