The module will give an introduction to fundamental results and concepts in graph theory. Topics are likely to include Hamilton cycles, graph matchings, connectivity, graph colourings, planar graphs and extremal graph problems. For example a fundamental result in Graph Theory is Dirac's theorem. It gives a condition which ensures that a graph has a Hamilton cycle (ie a cycle which contains all vertices of the graph). Another example is the four colour theorem. It states that every planar map can be coloured with at most four colours such that adjacent regions have different colours (this can be translated into a graph colouring problem). Some of the ideas will also be applied to algorithmic problems for graphs.
Learning Outcomes
By the end of the module the student should be able to:
Be familiar with basic graph parameters and their relationships
Understand and be able to apply fundamental results on graphs
Understand how some problems can be modelled as algorithmic graph problems and should know approaches to solve them
Apply the basic techniques introduced in the lectures
Explore these topics beyond the taught syllabus
Assessment
19605-07 : Raw Module Mark : Coursework (100%)
Assessment Methods & Exceptions
3 hour Written Unseen Examination (80%); In-course Assessment (20%)
Other
Reading List
Bondy, J A & Murty, U S R. 1976. Graph Theory with Applications. North-Holland.
West, D. 2001. Introduction to Graph Theory. Prentice Hall.
Electronic Version: http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
Diestel, R. 2000. Graph Theory. 2nd ed. Springer Verlag.
