CSC 672: Advanced Graph Theory

Offered Under: M.Sc. in Computer Science (CSC)

Introduction and fundamental concepts, Structure and basic definition in graph theory, methodology, proofs, basic properties of graphs; graph operations and their symbolic designation. Orientation of graphs, associated matrices and their relationship. Groups; automorphism groups, symmetric graps, graph enumeration, Polya's power group enumeration theorem. Colourability : five colour theorem, four colour conjecture, Heawood map colouring theorem, critical graphs, homomorphism, chromatic polynomial. Graph algorithms: DFS for non-separable components, orderer trees, application of Hoffman tree to sort by merge technique, Catalan numbers, maxflow problem, Ford and Flukerson's algorithms, Dinic's algorithm, Zero-one net flow, maximum matching in bipartite graphs, NP-complete problems, vertex cover, Hamiltonian paths and circuits, colouring, Steiner tree; max-cut, multicommodity integral flow.

  • None

Course Type Major
Credit Hour 3
Lecture Hour 45
Expected Outcome(s):

Suggested Books:

Grading Policy: