discipline

 Mathematics, Applied mathematics

subject

 Graph theory

lecturers

 András Frank

credits

 

period

 1 or 3

curriculum

Basic techniques: algorithmic proofs, separation along tight sets, the

splitting off operation, the uncrossing technique. Perfect graphs and Lovasz' perfect graph theorem. Theorems of Kuratowski (planar graphs), Tutte (3-connected graphs), Brooks (colouring), Tutte (perfect matching),  Edmonds (disjoint arborescences), Tutte (disjoint trees).  Orientation theorems (Robbins, Nash-Williams). Splitting theorems of Lovasz and Mader. Undirected edge-connectivity augmentation by Watanabe and Nakamura and its directed counterpart. Theorem of Lucchesi and Younger. Konig's edge-colouring theorem. Stable  matchings and Galvin's list colouring theorem. Edge-disjoint paths (Rothschild-Whinston, Lovasz-Cherkassky.) 

literature

 

form of tuition

Lectures

mode of assessment

written/oral exam