Course Details in

If you find any data displayed on this website that should be amended, please contact the Curriculum Management Team.

Module Title Graph Theory Mathematics Mathematics 06 19605 Deryk Osthur & Allan Lo Masters Level 20 Semester 1 LC Algebra & Combinatorics 1 - (06 25659) Optional for all MSci programmes in Mathematics and all MSci JH programmes including Mathematics Lecture-46 hours Tutorial-10 hours Total: 56 hours 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. By the end of the module the student should be able to:Be familiar with basic graph parameters and their relationshipsUnderstand and be able to apply fundamental results on graphsUnderstand how some problems can be modelled as algorithmic graph problems and should know approaches to solve themApply the basic techniques introduced in the lecturesExplore these topics beyond the taught syllabus 19605-07 : Raw Module Mark : Coursework (100%) 2 hour Written Unseen January Examination (80%); In-course Assessment (20%). West, D. 2001. Introduction to Graph Theory. Prentice Hall. Diestel, R. 2000. Graph Theory. 2nd ed. Springer Verlag. Electronic Version: http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html Bondy, J A & Murty, U S R. 1976. Graph Theory with Applications. North-Holland.