Module and Programme Catalogue

Search site

Find information on

2024/25 Taught Postgraduate Module Catalogue

COMP5940M Graph Theory: Structure and Algorithms

15 creditsClass Size: 40

Module manager: Dr Bogdan Alecu

Taught: Semester 2 (Jan to Jun) View Timetable

Year running 2024/25

Pre-requisite qualifications

Students must have studied one of the prerequisite modules below, or a module at an equivalent level. A solid mathematical foundation is desirable.


COMP3940Graph Algorithms and Complexity Theory
MATH3033Graph Theory

This module is not approved as an Elective

Module summary

Graphs are an extremely powerful tool for modelling real-world systems. They have applications in logistics, telecommunication, molecular biology, industrial engineering, linguistics, chemistry, and many other areas. However, many of the optimisation problems arising from these applications are computationally hard when there are no restrictions on the input. Thankfully, the scenarios that we aim to model often impose additional conditions on the structure of the corresponding graphs. This module focuses on how that structural information can be used to solve the relevant optimisation problems efficiently, with an emphasis on mathematical rigour.


This module aims to:
• motivate the study of graphs through examples of real-life inspired scenarios

• introduce the terminology required to talk about structural features of graphs

• illustrate a range of techniques for making use of these structural features

• provide an overview of the field, including some milestone results, as well as the guiding questions that led to them

• foster an appreciation of the mathematical way of thinking, and of the way it is applied to the study of graphs

Learning outcomes
On completion of the module, students should be able, in the context of working with graphs, to:
• understand and manipulate abstract concepts

• extract useful information from a complex system with many moving parts

• transform an intuitive, heuristic argument into a formal, rigorous one

• recognise faulty reasoning, and correct it

• identify structural features of graphs that are likely to yield good algorithmic behaviour

• use these structural features to design efficient algorithms for optimisation problems

• rigorously prove related results such as correctness of these algorithms

• wield various theoretical tools to derive these results


The main syllabus covers the following:
• the motivating example of interval graphs

• the terminology of hereditary classes, minimal forbidden induced subgraph characterisations, and graph parameters

• vertex colourings and the chromatic number

• comparability graphs

• chordal graphs

• basic Ramsey theory

• treewidth

Additional topics may be covered, such as perfect graphs, chi-boundedness, and graph decompositions.

Teaching methods

Delivery typeNumberLength hoursStudent hours
Private study hours117.00
Total Contact hours33.00
Total hours (100hr per 10 credits)150.00

Opportunities for Formative Feedback

There will be weekly problem classes, as well as a dedicated weekly office hour to support the module. In addition, there will be formative MCQs.

Methods of assessment

Assessment typeNotes% of formal assessment
Total percentage (Assessment Coursework)30.00

This module is re-assessed by exam only.

Exam typeExam duration% of formal assessment
Open Book exam2 hr 00 mins70.00
Total percentage (Assessment Exams)70.00

This module is re-assessed by exam only.

Reading list

The reading list is available from the Library website

Last updated: 29/04/2024 16:12:35


Browse Other Catalogues

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD

© Copyright Leeds 2019