Combinatorics and graphs II (NDMI012)

Jan Hubička,

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