MA4J3 Graph Theory
Lecturer: Vadim Lozin
Term(s): Term 1
Status for Mathematics students: List C
Commitment: 30 lectures
Assessment: 3 hour examination (100%)
Prerequisites: Familiarity with MA241 Combinatorics and MA252 Combinatorial Optimisation will be useful
Leads To:
Content:
Graph theory is a rapidly developing branch of mathematics that finds applications in other areas of mathematics as well as in other fields such as computer science, bioinformatics, statistical physics, chemistry, sociology, etc. In this module we will focus on results from structural graph theory. The module should provide an overview of main techniques with their potential applications. It will include a brief introduction to the basic concepts of graph theory and it will then be structured around the following topics:
Structural graph theory:
 Graph decompositions
 Graph parameters
Extremal graph theory:
 Ramsey’s Theorem with variations
 Properties of almost all graphs
Partial orders on graphs:
 Minorclosed, monotone and hereditary properties
 Wellquasiordering and infinte antichains
Aims:
To introduce students to advanced methods from structural graph theory.
Objectives:
By the end of the module the student should be able to:
 State basic results covered by the module
 Understand covered concepts from graph theory
 Use presented graph theory methods in other areas of mathematics

Apply basic graph decomposition techniques
Books:
Bollobás, Béla (2004), Extremal Graph Theory, New York: Dover Publications, ISBN 9780486435961
Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: SpringerVerlag, ISBN 9783540261834