Combinatorics and Graph Theory II
Lecture on Tuesday 14:00, S11
The tutorials will be led by Andreas
Feldmann on Thursday at 9:00 in S10.
This page will contain brief summaries of lectures with links to
relevant literature. See the syllabus
in SIS. The contents of the lecture will probably closely match last year's version.
- 2. 10.: Characterisation of maximum matchings via augmenting
paths. Blossom contraction and its relationship to maximum matchings.
Edmonds' Blossom algorithm for finding a maximum matching
in a graph [Blo,T].
- 9. 10.: Tutte's theorem on perfect matchings, Petersen's theorem [D].
- 16. 10.: Lemma on contractible edge for 3-connected graphs,
Tutte's characterisation of 3-connectivity [D], Kuratowski's and
Wagner's theorem [D].
[Ba] P. Bartlett: Chordal
graphs (pdf lecture notes)
[BCh] The Bondy
and Chvátal theorem
[Bo] B. Bollobás: Modern Graph Theory
[D] R. Diestel: Graph Theory
[HR] Y. Haimovitch, A. Raviv: Chordal
graphs (pdf slides)
[T] R. Tarjan: Sketchy
notes on [...] blossom algorithm for general matching
[W] H. Wilf: Generatingfunctionology