Selected topics in graph theory (third edition)

Fall semester 2018/19

Table of contents

News

General info

Fall semester 2018/2019.
Course in USOS.
Webpage of the first edition, webpage of the second edition.

Lecturers

Irene Muzi and Marcin Pilipczuk.

Grading

  1. Final grade is based on homeworks and final oral exam.
  2. We plan four homework assignments, each consisting of at least three problems. Each homework assignment should be submitted either by email or in a hard copy at the lecture on the day of the deadline.
  3. Each homework problem is worth 10 points. At the end of the semester we give a tentative grade, based on the number of points from the homework. We guarantee that 40 points will be enough for a passing grade.
  4. During the oral exam, one can modify the tentative grade by one of the values -1, -0.5, 0, +0.5, +1.0, +1.5. Not attending the exam results in the -1 modifier. If the final grade is lower than 3, it becomes 2.

Lecture plan

The lectures will be split into four parts.
  1. Graphs on surfaces (2 lectures)
  2. Graph minors (6 lectures)
  3. Expanders (4 lectures)
  4. Colourings (2 lectures)
More detailed plan:
No Date Plan Notes
1 8.10 Embeddings of graphs on surfaces. Combinatorial embeddings. Genus. Finding shortest noncontractible cycle in an embedded graph.  
2 15.10 Embeddings continued. Embeddings of large face-width. Announcing first homework assignment.
3 22.10 Introduction to the theory of graph minors. Treewidth.  
4 29.10 Brambles and well-linked sets.  
5 5.11 Tangles. Kruskal's theorem. Deadline of the first homework assignment.
6 19.11 Structure theorem for graphs excluding a fixed minor. Sketch of the Robertson-Seymour theorem. Announcing second homework assignment.
7 26.11 Grid minor theorem.  
8 3.12 Graph minors in planar graphs. Linear grid minor theorem. The ratcatcher algorithm.  
9 10.12 Introduction to expanders. Deadline of the second homework assignment.
10 17.12 Random walks in expanders. Announcing third homework assignment.
11 07.01 The zig-zag product of graphs.  
12 14.01 Proof that undirected reachability is in LOGSPACE (L=SL).  
13 21.01 Colourings of planar graphs. The five- and four-colour theorem. Five-choosability of planar graphs. Discharging. Perfect graphs. Announcing fourth homework assignment. Deadline of the third homework assignment.

Homeworks

Homework solutions should be submitted by the end of the tutorial on the date of the deadline, either by email or as a hard copy.
No Announced Deadline
Assignment 1 15.10 (lecture 1) 5.11 (lecture 5)
Assignment 2 19.11 (lecture 6) 10.12 (lecture 9)
Assignment 3 17.12 (lecture 10) 21.01 (lecture 13)
Assignment 4 21.01 (lecture 13) 4.02 (Monday, 2nd week of exam session)

Literature

  1. Reinhard Diestel, Graph Theory, Springer-Verlag 2005. PDF version.
  2. Bela Bollobas, Modern Graph Theory, Springer 1998.
  3. Mike Krebs, Anthony Shaheen, Expander Families and Cayley Graphs: A Beginner's Guide, Oxford University Press, USA, 2011.
  4. Bojan Mohar, Carsten Thomassen: Graphs on Surfaces, Johns Hopkins University Press, 2001.
  5. Some papers on the web, such as: