TUM – TUM – Menü

 

 
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)
ECTS: 5 ECTS
Language: English
TUM Online: Lecture - Module

News

  • The retake exam will be on September 24, 9-10 a.m. in room MI HS 2.

Lecture notes

Lecture notes will be provided, containing an overview of definitions and theorems. Proofs are not included.

Exercises

Please prepare solutions to the problems, so we can discuss them during class.

Sheet I pdf May 3  
Sheet II pdf May 8 Solution to Exercise II.3
Sheet III pdf May 15  
Sheet IV pdf May 22  
Sheet V pdf May 29 Solution to Exercise V.5
Sheet VI pdf June 5  
Sheet VII pdf June 12 Solution to Exercise VII.5
Sheet VIII pdf June 19  

Dates

The 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 pm–1:45 pm MI 02.04.011
Lecture Friday 12:15 pm–1:45 pm MI 02.04.011
Exercises Wednesday 12:15 pm–1:45 pm MW 1050

The tentative list of lecture dates is as follows.

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)

The last lecture is a bonus lecture without exercises.

Exam

The 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.

Contents

1. 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.

Literature

  • 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.

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.