Structural Graph Theory

Winter 2016/17


Course Schedule

Topics and Prerequisites

Final Exam and Requirements


Course Progress


Piotr Micek
Arnimallee 3, Rm 207
firstname.lastname at
Top of page

Course Schedule

Lectures will take place in Takustr 9, Room 46, on Tuesdays from 14:15 to 15:45.
Exercise classes will take place in Takustr 9, Room 55, on Wednesdays from 14:15 to 15:45.

On the first week, the exercise class will be replaced with a second lecture.
Top of page

Course description


Topics include: Graph Minor Theory: Tutte's lemma: generating 3-connected graphs; Kuratowski theorem: characterization of planar graphs; Mader's theorem: every graph with large average degree has a large clique minor; treewidth, brambles and tangles: treewidth duality theorem; excluded grid theorem; 2-disjoint rooted paths problem and Seymour's theorem; graph minor theorem for surfaces; statement(s) of the graph minor theorem. Sparsity: classes with bounded expansion; nowhere dense classes; characterisations, examples, current research.


Discrete Mathematics I or equivalent (basic combinatorics and graph theory).


BMS: advanced course; FU Master: Discrete Mathematics III modul or Ergäzungsmodul.
Top of page


Homework assignments will be posted below, and should be submitted before 8:00am of the due day.

Top of page
Assignment Due date
Sheet 1 26/10/2016
Sheet 2 08/11/2016
Sheet 3 16/11/2016
Sheet 4 (updated 25/11 15:45) 30/11/2016
Sheet 5 07/12/2016
Sheet 6 (Diestel's paper [pdf]) 14/12/2016
Sheet 7 (a survey about tangles by Martin Grohe [pdf]; Graph Minors X by Neil Robertson and Paul Seymour[pdf]) 18/01/2017
Sheet 8 (here are the videos of the series of lectures that I am following with you these days) 25/01/2017
for the "Sheet 9", please watch Lecture 7 by Jim Geelen (Oct 3, 2016) and read section 12.5 of Diestel's book (5th edition!); among other things Geelen states an upgrade of the Grid Theorem: "A grid from a tange" or more precisely the theorem given around '35. As an exercise write down a sketch of the proof. As the second exercise I want you to understand the statement of the Tangle-Tree Theorem given at the same lecture and its proof given by Diestel. Is it the same proof as the one sketched by Geelen? I'm not sure ... 01/02/2017