Topics in Graph Theory, 7.5 Credits

Contents

In this course, advanced techniques for studying graph colouring, factors in graphs and the theory of cycles in graphs are introduced. On the topic of graph colouring, the graph polynomial is defined, and connections between its coefficients and graph colourings and orientations are discussed. Latin squares are treated in this context as an application of the graph polynomial. Existence questions for different types of directed cycles are studied, along with connections to other structures. I the context of the thoery of cycles, conditions for when a matching is contained in a Hamiltonian cycle or a Hamiltonian path are studied.

Expected learning outcomes

For a passing grade, the student must be able to:

• define the graph polynomial and account for connections to colourings and orientations of graphs
• state and prove Hajos' theorem on the structure of q-chromatic graphs
• account for connections between Tutte's theorem, Ford-Fulkerson's theorem and factors in graphs
• state and prove conditions on the existence of long cycles in graphs
• state and apply algorithms to count Euler cycles in graphs
• state and apply the hopping lemma to prove the existence of long cycles
• state, apply and prove central theorems treated in the course

Required Knowledge

The course requires a course in Graph Theory on advanced level. Proficiency in English equivalent to Swedish upper secondary course English A (IELTS (Academic) with a minimum overall score of 5.5 and no individual score below 5.0. TOEFL PBT (Paper-based Test) with a minimum total score of 530 and a minimum TWE score of 4. TOEFL iBT (Internet-based Test) with a minimum total score of 72 and a minimum score of 17 on the Writing Section). Where the language of instruction is Swedish, applicants must prove proficiency in Swedish to the level required for basic eligibility for higher studies.