Math 6430 Graph theory

Description

This is a graduate level course that builds upon concepts presented in introductory undergraduate courses in Graph Theory. While the field of Graph Theory is rich and diverse, this course considers focusses on three selected topics, going into greater depth than is experienced in undergraduate courses. An emphasis is placed upon proofs and proof techniques which in turn provides preparation for future research and study.

The topics for the course typically include:

  • Matchings: matchings, covers, the König-Egerváry theorem, Hall's theorem, Tutte's 1-factor theorem
  • Connectivity: connectivity and edge-connectivity, Menger's theorem, Dirac's fan lemma, Mader's theorem for vertex-transitive graphs
  • Network flows: networks, flows, cuts, the Ford-Fulkerson algorithm, Menger's theorem, circulations

Prerequisites

An introductory undergraduate course in Graph Theory
or permission from the instructor.

References

  • J.A. Bondy and U.S.R. Murty. Graph theory. Springer, 2008.
  • R. Diestel. Graph theory, third edition. Springer, 2005.
  • D.B. West. Introduction to graph theory, second edition. Prentice-Hall, 2001.

Contact

Mathematics and Statistics

230 Elizabeth Ave, St. John's, NL, CANADA, A1B 3X9

Postal Address: P.O. Box 4200, St. John's, NL, CANADA, A1C 5S7

Tel: (709) 864-8000