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