Forschungsinstitut für Diskrete Mathematik

Hauptseminar Diskrete Optimierung

Wintersemester 2011/12

Thema: Graphentheorie

In diesem Seminar werden ausgewählte Themen aus der Graphentheorie behandelt, die über den Stoff der Vorlesungen hinausgehen. Themen sind unter anderem gruppenwertige Flüsse, Hamiltonkreise, Graphenfärbungen, Graphpartitionierungen und das Packen von Arboreszenzen. Als Quellen dienen Kapitel aus den Büchern von Diestel und Frank sowie Originalarbeiten.

Nr.	Probevortrag 12 Uhr c.t.	Vortrag 14 Uhr c.t.	Name	Thema	Betreuung
1	26.9.	10.10.	Christoph Matzke	Group-valued flows and k-flows for small k	Jens Maßberg
2	4.10. (Dienstag)	17.10.	Christian Stegemann	Flow-colouring duality	Jens Maßberg
3	10.10.	24.10.	Martin Burek	Tutte's flow conjectures	Christoph Bartoschek
4	17.10.	31.10.	Salah Zayakh	Szemerédi's regularity lemma	Christian Schulte
5	24.10.	7.11.	Nils Hoppmann	Applying the regularity lemma	Christian Schulte
6	31.10.	14.11.	Patrick Schmitz	Random Graphs	Christoph Bartoschek
7	7.11.	21.11.	Marcel Haubrich	Hamilton cycles: necessary and sufficient conditions	Jan Schneider
8	14.11.	28.11.	Daniel Romen	Hamilton cycles in the square of a graph	Jan Schneider
9	21.11.	5.12.	Vitali Kurnatowski	Computing roots of graphs is hard	Christian Schulte
10	28.11.	12.12.	Justus Winkelmann	The chromatic number of graph powers	Dirk Müller
11	5.12.	19.12.	Rasmus Schroeder	On the hardness of 4-coloring a 3-colorable graph	Michael Gester
12	12.12.	9.1. (12 Uhr c.t.)	Nicolas Kämmerling	Enumerating maximal independent sets with applications to graph coloring	Michael Gester
13	19.12. (16 Uhr c.t.)	9.1.	Christoph Hunkenschröder	An O*(2^n) algorithm for graph coloring	Dirk Müller
14	19.12.	16.1.	Markus Ahrens	Approximate graph coloring by semidefinite programming	Michael Gester
15	6.1. (13 Uhr c.t.)	23.1.	Friedrich Saas	Packing arborescences	Ulrike Suhl
16	16.1.	30.1.	Michael Link	Packing branchings	Ulrike Suhl

Literatur:

R. Diestel: Graph Theory, 3rd edition, Springer, 2005
A. Frank: Connections in Combinatorial Optimization, Oxford University Press, 2011.

Eine Liste aller Vorträge mit Quellenangaben ist hier verlinkt.

Von allen Teilnehmerinnen und Teilnehmern werden eine regelmäßige Teilnahme und eine aktive Mitarbeit erwartet.
Die Vorträge sollen höchstens 75 Minuten dauern. Anschließend sind dann 15 Minuten für eine Diskussion vorgesehen.
Alle Teilnehmerinnen und Teilnehmer müssen eine Zusammenfassung ihres Vortrags anfertigen, die mindestens eine und höchstens zwei Seiten lang ist.
Alle Teilnehmerinnen und Teilnehmer müssen außerdem einen Probevortrag halten, der zwei bis drei Wochen vor dem eigentlichen Vortrag statfindet. Ein erfolgreicher Probevortrag ist Voraussetzung für den Vortrag im Seminar.

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Jun.Prof. Dr. S. Held,
Dr. U. Brenner