# 2024/25 Taught Postgraduate Module Catalogue

## COMP5940M Graph Theory: Structure and Algorithms

### 15 creditsClass Size: 40

Module manager: Dr Bogdan Alecu
Email: B.Alecu@leeds.ac.uk

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.

### Pre-requisites

 COMP3940 Graph Algorithms and Complexity Theory MATH3033 Graph 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.

### Objectives

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

### Syllabus

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 type Number Length hours Student hours Lectures 22 1.00 22.00 Tutorial 11 1.00 11.00 Private study hours 117.00 Total Contact hours 33.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

Coursework
 Assessment type Notes % of formal assessment Assignment Coursework 10.00 Assignment Coursework 10.00 Assignment Coursework 10.00 Total percentage (Assessment Coursework) 30.00

This module is re-assessed by exam only.

Exams
 Exam type Exam duration % of formal assessment Open Book exam 2 hr 00 mins 70.00 Total percentage (Assessment Exams) 70.00

This module is re-assessed by exam only.