620-352 Graph Theory

Credit Points

Coordinator

Prerequisites

620-112 or 620-122 or 620-142 or 620-200 or 620-211.

Semester

Contact

Subject Description

This subject introduces the basic concepts of graph theory including paths and cycles, trees and counting, automorphism groups, planar graphs, colouring properties, chromatic polynomials, matching theory. Students should develop the ability to implement algorithms on graphs for finding objects such as minimum spanning trees, maximum matchings and flows; and to implement approximation algorithms. This subject demonstrates the variety of applications of graph theory both within and outside mathematics.

Introduction to Graph Theory: Basic concepts, paths and cycles, trees and counting, automorphism groups; planar graphs, colouring properties, chromatic polynomials, matching theory, probabilistic method. Algorithms: Minimum spanning trees, maximum matchings, flows, approximation algorithm.

Assessment

Up to 26 pages of written assignments and a 3-hour end-of-semester written examination.