Webrelaunch 2020

Seminar (Graph Colouring) (Winter Semester 2014/15)

This is a reading seminar based on the book Graph Colourings and the Probabilistic Method by Michael Molloy and Bruce Reed. Every student presents a part of this book in a talk.

A succesful participation includes:

  • presence
  • participation
  • a good talk
Seminar: Wednesday 11:30-13:00 1C-01
Wednesday 11:30-13:00 SR 3.68


  • basic knowledge of graph theory and probability theory


  • Every student gives a talk on a chapter of the book assigned to him/her.
  • Every student attends two weeks before his/her talk personal meeting with Mr. Ueckerdt.
  • Every speaker may use the blackboard, the beamer and overhead transparencies. Handouts are optional.


#part of the bookspeakerpages
1.First Moment MethodJohannes27-36
2.The Lovasz Local Lemma and The Chernoff BoundMatthias39-46
3. Hadwiger's ConjectureXizhe49-53
4.Total Colouring RevisitedDaniel67-75
5.Talagrand's InequalityAnnika79-89
6.Talagrand's InequalityJennifer79-89
7.Azuma's InequalityFabian91-103
8.Strucutral DecompositionFelix157-167
9.Chi, Omega and DeltaTorsten--
10.Near Optimal Total Colouring IAlexander185-191
11.Generalizations of the Local LemmaAnnette221-229
12.Finding Fractional ColouringsValentin239-246
13.Conditional Expectation and Algorithmic Local LemmaOussama287-291, 295-300