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.
FSF3700 Graph Theory 7.5 credits
This course has been discontinued.
Decision to discontinue this course:
No information inserted
Information per course offering
Course offerings are missing for current or upcoming semesters.
Course syllabus as PDF
Please note: all information from the Course syllabus is available on this page in an accessible format.
Course syllabus FSF3700 (Spring 2019–)Headings with content from the Course syllabus FSF3700 (Spring 2019–) are denoted with an asterisk ( )
Content and learning outcomes
Course contents
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.
Literature
"Graph Theory, (3rd edition)", by Reinhard Diestel, GTM Springer Verlag
Examination and completion
Grading scale
P, F
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.
If the course is discontinued, students may request to be examined during the following two academic years.
Written and oral presentations.
Other requirements for final grade
Approved written and oral presentations
Examiner
No information inserted
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.
Further information
Course room in Canvas
Registered students find further information about the implementation of the course in the course room in Canvas. A link to the course room can be found under the tab Studies in the Personal menu at the start of the course.
Offered by
Education cycle
Third cycle