Graphentheorie II

Inhalt

Wir werden uns Elementen der Graphentheorie zuwenden können, deren Behandlung schon einiger Erfahrung bedarf: Dazu gehören die modernen Sätze über Zusammenhang und Verbindbarkeit (Kapitel 2), Extremalsätze für Minoren (Kapitel 6), aber auch die Ramsey-Theorie für induzierte Teilgraphen und Fleischners Satz (Kapitel 8). Diese Auswahl liegt dem Schwierigkeitsgrad nach in der Nähe der Anwendungen des Regularitätslemmas aus dem ersten Teil. Im Anschluß daran werden wir leichtere Themen "algebraischeren" Charakters behandeln: Packungs- und Überdeckungssätze (Kapitel 1), der Zyklenraum und seine Verwandten sowie geometrische und algebraische Dualität (Kapitel 0 und 3), perfekte Graphen (Kapitel 4), und Flüsse (Kapitel 5). Der Stoff des 10ten Kapitels wird gesondert im Seminar behandelt.

Vorkenntnisse

Vorkenntnisse im Umfang der Graphentheorie I.

Skript und Literatur

Die Vorlesung folgt, wie auch der erste Teil, dem Buch Graphentheorie von Reinhard Diestel. Die dritte Auflage ist erschienen beim Springer-Verlag Heidelberg (2006).

Das Werk ist elektronisch verfügbar auf Reinhard Diestels Homepage.

Verlauf

Vorlesungsstoff Graphentheorie I & II.

• Kapitel 0 Abschnitte 1,2,3,4,5,6,7,8,9,10.
• Kapitel 1 Abschnitte 1,2,4,5 (ohne 1.2.3).
• Kapitel 2 Abschnitte 1,2,3,4,5 (ohne 2.1.3, 2.3.2, 2.3.3, den dritten Beweis von 2.3.1; mit 2.1.2, 2.1.4, 2.2.3, 2.5.3, 2.5.4).
• Kapitel 3 Abschnitte 1,2,4,5,6.
• Kapitel 4 Abschnitte 1,2,3,4.
• Kapitel 5 Abschnitte 1,2,3,4,5,6.
• Kapitel 6 Abschnitte 1,2,3,4 (ohne den Beweis von 6.2.1, 6.2.5, 6.3.8, 6.3.9)
• Kapitel 7 Abschnitte 1,2.
• Kapitel 8 Abschnitte 1,2 (mit Chvátals Vermutung).
• Kapitel 9 Abschnitte 1,2,3,4 (ohne 9.3.5).

Übungsaufgaben (am Ende des jeweiligen Kapitels, Numerierung der 3ten Auflage)

• Aufgaben zum 10.7.2007: Kapitel 3, Aufgaben 28(+),29,31,33.
• Aufgaben zum 26.6.2007: Keine.
• Aufgaben zum 19.6.2007: Kapitel 0, Aufgaben 30,32,33,37,38(+).
• Aufgaben zum 12.6.2007: Kapitel 5, Aufgaben 12,13,14(-),15,20(+).
• Aufgaben zum 22.5.2007 & 5.6.2007: Kapitel 5, Aufgaben 1(-),2,3(+),4(-),5(-).
• Aufgaben zum 15.5.2007: Keine.
• Aufgaben zum 8.5.2007: Kapitel 1, Aufgabe 23. Zeigen Sie, daß zu je k Kanten eines 2k-kantenzusammenhängenden Graphen k kantendisjunkte Spannbäume existieren, die jeweils eine dieser Kanten enthalten. Zeigen Sie, daß jeder Graph mit zwei kantendisjunkten Spannbäumen einen aufspannenden Eulerschen Teilgraphen besitzt.
• Aufgaben zum 18.4.2007: Kapitel 2, Aufgabe 24. Zeigen Sie (-), daß ein Graph genau dann k-verbunden ist, wenn er wenigstens 2k Ecken hat und jede Menge von genau 2k Ecken verbunden ist.
• Aufgaben zum 11.4.2007: Kapitel 2, Aufgaben 17,18-,19.