Logik in der Informatik Prof. Dr. Martin Grohe

Aktuelles

• Übungsblatt 7.

Einleitung

Graph Minor Theory is one of the deepest branches of graph theory. A starting point for this theory is Kuratowski's characterisation of planar graphs as precisely those graphs that do not contain the complete graph with 5 vertices and the complete bipartite graph with 3 vertices on both sides as a minor. Robertson and Seymour's Graph Minor Theorem is a far reaching generalisation of Kuratowski's Theorem, which among other things implies an analogue of Kuratowski's Theorem for graphs embeddable in higher surfaces. The minor relation may be viewed as some form of a topological subgraph relation: a graph G is a minor of a graph H if G can be obtained from H by deleting edges or vertices and contracting edges.

To prove the Minor Theorem, Robertson and Seymour developed a structure theory for graphs excluding other graphs as minors. This structure theory has found many applications besides the proof of the Minor Theorem, among them substantial algorithmic applications.

This course will be an introduction into graph minor theory and its applications. As a prerequisite, only basic knowledge of graph theory and algorithms will be assumed. Any standard course on discrete mathematics or on algorithms should provide this knowledge.

Inhaltsverzeichnis und Skript

Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert wird. Soweit es ein Skript gibt, ist dies durch Anklicken der entsprechenden Kapitel zugänglich.

Titel und Inhaltsverzeichnis

0. Grundlagen
1. Einführung
2. Planare Graphen
3. Baumzerlegungen
4. Verbotene Wälder
5. Verbotene planare Graphen
6. Verbotene vollständige Graphen
7. Wohlquasiordnungen
8. Eine Verallgemeinerung des Satzes von Kuratowski

Literaturverzeichnis

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen und gelegentlich ergänzende Bemerkungen.

Information zur Vorlesung

Zeit und Ort

Dienstag und Donnerstag 9:15-10:45 Uhr,
Erwin Schrödinger Zentrum (Rudower Chaussee 26, Berlin Adlershof) Raum 1'307

 

Dozent

Martin Grohe

Sprechstunden: Donnerstags 16:00 - 17:00 Uhr

Übungen

Zeit und Ort

Donnerstag 11:15 - 12:45 Uhr,
Erwin Schrödinger Zentrum (Rudower Chaussee 26, Berlin Adlershof) Raum 1'307

 

Übungsleiterin

Magdalena Grüber

Sprechstunden: Donnerstags 17:00 - 18:00 Uhr

Übungsaufgaben

• Blatt 1 (23.4.2009; Abgabe am 30.4.2009)
• Blatt 2 (30.4.2009; Abgabe am 7.5.2009)
• Blatt 3 (14.5.2009; Abgabe am 26.5.2009)
• Blatt 4 (28.5.2009; Abgabe am 4.6.2009)
• Blatt 5 (18.6.2009; Abgabe am 25.6.2009)
• Blatt 6 (25.6.2009; Abgabe am 2.7.2009)
• Blatt 7 (9.7.2009; Abgabe am 16.7.2009)

---

Prüfungen

Zu Beginn der Semesterferien finden mündliche Prüfungen statt.

---

Literatur

Es gibt bisher keine Lehrbücher zur Minorentheorie. Ein gute Einführung in die Graphentheorie und speziell auch in die Minorentheorie ist Diestel's Buch. Teile des Vorlesungsstoffes finden sich auch im Buch von Mohar und Thomassen.

• R. Diestel, Graph Theory, Third Edition, Springer Verlag, 2005.
• B. Mohar and C. Thomassen, Graphs on Surfaces. Johns Hopkins University Press, 2001.

Wesentliche Teile des Vorlesungsstoffes stammen aus folgender Serie von Artikeln:

• N. Robertson and P. Seymour, Graph Minors I-XXIII. Sind erschienen oder werden erscheinen im Journal of Combinatorial Theory, Series B.

Weitere Literaturhinweise werden in der Vorlesung gegeben.

---

Last modified: Fri Jul 31 12:01:41 CEST 2009
Martin Grohe