Combinatorics and graphs II (NDMI012)

Office hours: by appointment (prefferably Tuesday or Wednesday). S322 (Malostranské nám. 25, 3rd floor).

October 1: Edmonds blossom algorithm [VM] (in Czech) [SV] [T] (None of texts proves lemma about blossom contraction correctly)
Practical: Lemma about blossom contraction
October 8: Tutte's theorem on perfect matchings, Petersen's theorem [D].
Practical: Finishing proof about blososm contraction. Hall theorem using Tutte's theorem
October 15: Lemma on contractible edge for 3-connected graphs, Tutte's characterisation of 3-connectivity [D], Kuratowski's and Wagner's theorem [D].
October 22: 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].
October 29: 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].
November 5: Brooks' theorem and Vizing's theorem [D]. Perfect graphs (introduction)
November 19: Perfect graphs, the weak perfect graph theorem [D].
November 26: Chordal graphs and their perfect elimination schemes [Ba, HR].
December 3: Bondy-Chvátal theorem [BCh]. Lecture of Arnaud Pecher

Homeworks