Advanced Topics in Graph Theory (MA 5214)
Lecture (John-von-Neumann Lecture)
|Lectures:||Prof. Marc Noy|
|Exercises:||Carl Georg Heise|
|Format:||2+1 SWS (partly blocked)|
|TUM Online:||Lecture - Module|
- The retake exam will be on September 24, 9-10 a.m. in room MI HS 2.
Lecture notesLecture notes will be provided, containing an overview of definitions and theorems. Proofs are not included.
ExercisesPlease prepare solutions to the problems, so we can discuss them during class.
|Sheet I||May 3|
|Sheet II||May 8||Solution to Exercise II.3|
|Sheet III||May 15|
|Sheet IV||May 22|
|Sheet V||May 29||Solution to Exercise V.5|
|Sheet VI||June 5|
|Sheet VII||June 12||Solution to Exercise VII.5|
|Sheet VIII||June 19|
DatesThe course consists of twelve lectures, starting on April 30, 2013. Lectures will be given twice a week (with exceptions), exercises take place once a week.
|Lecture||Tuesday||12:15 pm1:45 pm||MI 02.04.011|
|Lecture||Friday||12:15 pm1:45 pm||MI 02.04.011|
|Exercises||Wednesday||12:15 pm1:45 pm||MW 1050|
|April 30||Introduction||May 28||Colourings|
|May 3||Matchings||May 31||Minors|
|May 7||Connectivity||June 4||Minors|
|May 14||Planarity||June 7||Tree-width|
|May 17||Planarity||June 18||Tree-width|
|May 24||Colourings||June 21||Well quasi-ordering|
|June 25||Bonus presentations||June 28||Exam (MW 1350)|
ExamThe exam will take place on June 28 during the normal time of the lecture in room MW 1350. The exam starts at 12:15 p.m., so please try to be there by noon. You have 60 minutes for the exam. There are no utilities or notes allowed. The exam is a written exam. Registration for the exam via TUMOnline is mandatory for participation for the exam, registration for the lecture and/or the exercises is not sufficient. There will be a bonus for the exam, which can be achieved by working on certain small projects on topics that are not covered in the lectures but are natural extensions. Details will be announced in the lecture. If you receive the bonus, your grade on the final exam will be improved by one third (i.e. 1.7 to 1.3, 2.3 to 2.0 etc.). A fail grade cannot be improved by the bonus and neither can a grade of 1.0. The bonus is only valid for the summer term 2013 (normal and re-take exam). The session for the presentation of the bonus projects will be on June 25.
Contents1. Matchings and coverings. Matchings in bipartite graphs: Hall's theorem. Stable matchings. Matchings in general graphs: Tutte's theorem. Vertex and edge coverings. 2. Connectivity. Structure of 2-connected and 3-connected graphs. Menger's theorem and applications. 3. Planar graphs. Connectivity of planar graphs. Kuratowski's theorem. Duality. Graphs on surfaces. 4. Colourings. The greedy algorithm and Brook's theorem. Edge colouring. List coloring of planar graphs and bipartite graphs. 5. Graph minors. Excluded minors. Planar and series-parallel graphs. Wagner's theorems: excluding K5 or K3,3. 6. Tree-width. Tree-decompositions and partial k-trees. Lower bounds. The excluded grid theorem. Erdös-Pósa property. 7. Algorithmic aspects of tree-width. Algorithms on trees: dynamic programming. Algorithms on graphs of bounded tree-width. Courcelle's theorem. 8. The graph minor theorem. Well quasi-orderings. Kruskal's theorem. Bounded tree-width. Obstructions for surfaces. The structure theorem and the graph minors theorem. Algorithmic consequences. The course assumes familiarity with the basic concepts of graph theory. Topics 1 to 4 are more classical, covering fundamental results such as the theorems of Hall, Tutte, Menger, Kuratowski, as well as more recent results. The main goal in this rst part is to learn the classical theory and proof techniques. The second part, topics 5 to 7, is an introduction to graphs minors and tree-width, which are at the core of current research on graph theory. Some key results will be proven in detail, while others will be only sketched. The main goal in this second part is to become acquainted with the theory of graph minors and its applications.
- R. Diestel. Graph Theory. 4th edition. Springer 2010.
- J.A. Bondy, U.S.R. Murty. Graph Theory. Springer 2008
- B. Mohar, C. Thomassen. Graphs on surfaces. John Hopkins U. Press 2001.
- D. West. Introduction to Graph Theory. Prentice-Hall 1996.