Combinatorics and Graph Theory II

Lecture on Tuesday 14:00, S11

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: