SF2740 Graph Theory
KTH Royal Institute of Technology
English B / English 6
Completed basic course SF1610 Discrete Mathematics, SF1662 Discrete Mathematics, SF1679 Discrete Mathematics or SF1688 Discrete Mathematics.
Basic concepts of graph theory: degree, distance, diameter, matching etc. Theory for matchings, in particular for bipartite graphs. Structure theorems about 2- and 3- connected components of graphs, also Mader’s and Menger’s Theorems. Theory about minors, planarity. Coloring of various kinds, Perfect graphs, Hadwiger’s conjecture, random graphs and the probabilistic method.
After the course the student should be able to
- explain basic concepts. theorems and proofs within the parts of graph theory described by the course content,
- use basic concepts. methods and theorems in graph theory to solve problems and communicate with the help of mathematical language.
Reviews
Improve accuracy by rating this course