FSF3700 Graph Theory 7.5 credits
This course has been discontinued.
Last planned examination: Autumn 2022
Decision to discontinue this course:
No information insertedContent and learning outcomes
Course contents
Theory for matchings. Structure theorems about 2 and 3- connected components of graphs, also Mader’s and Menger’s Thms. Theory anout minors, planarity. Coloring of various kinds, Perfect graphs, Hadwiger’s conjecture, random graphs and the probabilistic method. Szemeredi's regularity lemma and extremal graph theory, fast mixing and various algebraic techniques.
Intended learning outcomes
The aim of the course is to understand and be able to use more advanced theory and methods from the theory of graphs. The course can both be seen as a step stone to research in graph theory in mathematics or in applications in neighboring disciplines. After the student has finished the course he/she is expected to
- master the basic definitions and concepts of Graph theory.
- be able to formulate problems in graph theoretic terms.
- have increased ability in graph theoretic problem solving
- understand various versions of connectedness of a graph, understand structural theorems and be able to describe and use e.g. the theorems of Mader and Menger.
- Understand and be able to use the concept of a minor.
- Know about many different coloring problems for graphs. Be able to formulate applied problems as coloring problems.
- Understand and be able to use different models of random graphs and (random networks).
- Be able to do basic usage of the probabilistic method in graph theory.
- Be able to use the Regularity lemma know a proof.
- Know algebraic techniques to study graphs and problems on graphs.
Literature and preparations
Specific prerequisites
Mathematical knowledge corresponding to a Master in mathematics and at least one course with graph theory before.
Recommended prerequisites
Equipment
Literature
"Graph Theory, (3rd edition)", by Reinhard Diestel, GTM Springer Verlag
Examination and completion
If the course is discontinued, students may request to be examined during the following two academic years.
Grading scale
Examination
- INL1 - Assignment, 7.5 credits, grading scale: P, F
Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.
The examiner may apply another examination format when re-examining individual students.
Written and oral presentations.
Other requirements for final grade
Approved written and oral presentations
Opportunity to complete the requirements via supplementary examination
Opportunity to raise an approved grade via renewed examination
Examiner
Ethical approach
- All members of a group are responsible for the group's work.
- In any assessment, every student shall honestly disclose any help received and sources used.
- In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.