# 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.

#### Topics covered:

- 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].
- 23. 10.: Basic topological notions: homeomorphism, surface,
construction of surfaces by adding a handle or cross-cap,
classification of orientable and non-orientable surfaces (without
proofs) [D].
- 30. 10.: Generalized Euler's formula for graphs embeddable to a
given surface. Upper bounds for number of edges, minimum degree,
degeneracy and chromatic number for graphs embeddable to a given
surface [D].

- 13. 11.:Brooks' theorem and Vizing's theorem [D].
- 20. 11.:Perfect graphs, the weak and strong perfect graph
theorems (without proof) [D]. Comparability graphs and Dilworth's
theorem [Bal, D]. Chordal graphs and their perfect elimination schemes [Ba,
HR].
- 27. 11.: The Tutte polynomial - basic properties, recursive definition, relation to the chromatic polynomial [Bo].
- 4. 12.: Formal power series (with real coefficients), their
operations, existence of multiplicative inverses. Ordinary
combinatorial classes and their ordinary generating functions [W].
- 11. 12.: Exponential generating functions [W].
- 18. 12.: Basics of group actions, Burnside lemma (including its weighted form) [Bo].
- 8. 1.: Turán's theorem [D], Bondy-Chvátal and Dirac's theorems [BCh], Erdős-Ko-Rado theorem [EKR].

#### Literature:

[Bal] P. Ballen: Perfect
graphs and the perfect graph theorems (pdf introductory paper)

[Ba] P. Bartlett: Chordal
graphs (pdf lecture notes)

[BCh] The Bondy
and Chvátal theorem

[Blo] The
Blossom Algorithm

[Bo] B. Bollobás: Modern Graph Theory

[D] R. Diestel: Graph Theory

[EKR] The
Erdős-Ko-Rado theorem

[HR] Y. Haimovitch, A. Raviv: Chordal
graphs (pdf slides)

[T] R. Tarjan: Sketchy
notes on [...] blossom algorithm for general matching

[W] H. Wilf: Generatingfunctionology