CS60047 - Advanced graph theory

Brief Syllabus:

Matching and covering: Matching in bipartite graphs - Konig's theorem, Hall's marriage theorem. Matching in general graphs - Tutte's theorem. Path covers - Gallai-Milgram theorem, Dilworth theorem.

Connectivity: The structure of 2-connected graphs, structure of 3-connected graphs, Menger's theorem.

Planar graphs: Euler's formula, Wagner's theorem, Kuratowski's theorem.

Colouring: Five colour theorem for planar graphs, vertex colouring - Brooks' theorem, Edge colouring - Vizing's theorem.

Course books:

  • Graph Theory, by Reinhard Diestel.

  • Modern Graph Theory, by Bela Bollobas.

  • Graph Theory with Applications, by J. A. Bondy and U. S. R. Murty.

  • Introduction to Graph Theory, by Douglas B. West.