Course Code : PMAT 42983
Title : Graph Theory
Pre-requisites : PMAT 21553
Learning Outcomes:
At the end of the course the student should be able:
- recognize the appearance of graphs in real life,
- identify certain real life situations that can be described using graphs,
- apply the concepts of graphs to the real world problems.
Course Contents:
Matrices Associated with graphs and their properties, Trees: spanning trees of a connected graph, Coloring: Vertex colourings of graphs: greedy algorithm, Edge colourings of graphs, Matching and covering: Konigs theorem and Halls theorem, connectivity.
Random graphs: properties, Erdos¹s theorem on the existence of graphs with large girth and large chromatic number, the countably infinite random graph.
Group project: Applications related to real world problems
Method of Teaching and Learning: A combination of lectures, tutorial discussions.
Recommended Reading:
- Robin J. Wilson: Introduction to Graph Theory (5e) Longman, 2010
- Gary Chartrand, Ping Zhang: A First Course in Graph Theory Courier Corporation, 2013
- Balakrishnan: T&P Of Graph Theory (Schaum's outline series) Tata McGraw-Hill Education, 2004
- Dragos M. Cvetkovic, Michael Doob, Horst Sachs. Spectra of Graphs: Theory and Applications 3e Wiley, 1999