| CODE | MAT5417 | ||||||||
| TITLE | Selected Topics in Graph Theory | ||||||||
| UM LEVEL | 05 - Postgraduate Modular Diploma or Degree Course | ||||||||
| MQF LEVEL | 7 | ||||||||
| ECTS CREDITS | 15 | ||||||||
| DEPARTMENT | Mathematics | ||||||||
| DESCRIPTION | The statement of the four colour problem and its eventual extension to higher-order surfaces is considered to have given the birth to topological graph theory. In an attempt to solve this problem and other related questions, some researchers started studying in depth the structure of graphs, in particular how they can be drawn without having edge-crossings and how their connectivity properties can be utilised. With time, the study of crossing numbers developed as an area of its own, as did the study of connectivity. The ideas of connectivity are greatly exploited to examine the structure of graphs, which has recently seen a rapid increase in popularity due to its applicability in areas such as computer networks. The original colouring problem itself gave rise to a number of variants of a combinatorial flavour. Hence the choice of the topics selected for this study-unit. Content Crossing number: 鈥� Jordan Curve Theorem; 鈥� Crossing-critical graphs; 鈥� Rectilinear crossing number; 鈥� Results and conjectures related to families of graphs: complete, complete bipartite, generalized Petersen, Cartesian product, hypercubes; 鈥� Drawings on surfaces other than the sphere. Connectivity: 鈥� Vertex connectivity and edge connectivity; 鈥� Maximally connected graphs; 鈥� Super-connectivity; 鈥� Conditional-connectivity; 鈥� Results and conjectures related to families of graphs: p-partite graphs, Cartesian and Kronecker (Direct) products of graphs. Colouring: 鈥� Chromatic number and chromatic index; 鈥� Local chromatic number: Kneser graphs, Schrijver graphs, Mycielski graphs, Borsuk graphs; 鈥� Fractional chromatic number. Study-unit Aims: This study-unit is aimed to address topics in three main branches of graph theory, namely, topological graph theory, structural graph theory and combinatorial graph theory. It endeavours to discuss the interplay between these branches by exposing the students to the main techniques, results and open problems in the areas of crossing numbers, connectivity and colouring. These three topics are generally regarded to have laid the foundations of the work in the previously mentioned branches of graph theory and still generate a considerable amount of interest for current research. They thus offer an excellent opportunity to explore various aspects of graph theory and beyond. Learning Outcomes: 1. Knowledge & Understanding: By the end of the study-unit the student will be able to: - Recognise the main definitions and results underlying the topics covered within this study-unit; - Construct and structure proofs of the main results; - Describe the implications that these results had on the development of graph theory in general; - Build on these results by applying them to more recent problems in graph theory; - Analyse the interrelationships between the topics covered within this study-unit and with other branches of mathematics. 2. Skills: By the end of the study-unit the student will be able to: - Find, select and organise information gathered from different sources; - Critically examine results published in publications on graph-theory; - Apply a variety of techniques to solve problems and prove new results; - Present in a coherent and mathematically correct way old and new results in graph theory. Main Textbooks Beineke, L.W., & Wilson, R.J. (ed.) (2009) 鈥楨ncyclopedia of Mathematics and its Applications 128: Topics in Topological Graph Theory鈥�. UK: Cambridge University Press. Beineke, L.W., & Wilson, R.J. (ed.) (2013) 鈥楨ncyclopedia of Mathematics and its Applications 147: Topics in Structural Graph Theory鈥�. UK: Cambridge University Press. Simonyi, G., & Tardos, G. (2006) Local chromatic number, Ky Fan鈥檚 Theorem, and circular colorings, 鈥楥ombinatorica鈥�, 26 (5) pp.587鈥�626. Supplementary Readings Chartrand, G., Lesniak, L., & Zhang, P. (2010) 鈥楪raphs and Digraphs鈥� 5th Ed. Boca Raton: CRC Press. Chartrand, G., & Zhang, P. (2009) 鈥楧iscrete Mathematics and its applications: Chromatic Graph Theory鈥�. Boca Raton: CRC Press. |
||||||||
| ADDITIONAL NOTES | Pre-requisite Qualifications: B.Sc. with Mathematics as a main area Follows from: MAT3425 and MAT3410 |
||||||||
| STUDY-UNIT TYPE | Lecture and Independent Study | ||||||||
| METHOD OF ASSESSMENT |
|
||||||||
| LECTURER/S | |||||||||
|
The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints. Units not attracting a sufficient number of registrations may be withdrawn without notice. It should be noted that all the information in the description above applies to study-units available during the academic year 2025/6. It may be subject to change in subsequent years. |
|||||||||