SUBJECT
Title
Graph theory
Type of instruction
lecture
Level
master
Faculty
Part of degree program
Credits
3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
Graph orientations, connectivity augmentation. Matchings in not necessarily bipartite graphs, T-joins. Disjoint trees and arborescences. Disjoint paths problems. Colourings, perfect graphs.
Readings
András Frank: Connections in combinatorial optimization (electronic notes).
Further reading:
- W.J. Cook, W.H. Cunningham, W.R. Pulleybank, and A. Schrijver, Combinatorial Optimization, John Wiley and Sons, 1998.
- R. Diestel, Graph Theory, Springer Verlag, 1996.
- A. Schrijver, Combinatorial Optimization: Polyhedra and efficiency, Springer, 2003. Vol. 24 of the series Algorithms and Combinatorics.