Home | deutsch  |  Impressum  |  Data Protection  |  Sitemap  |  Intranet  |  KIT
Research Group on Discrete Mathematics

Kollegiengebäude Mathematik (20.30)
Room 1.044

Institut für Algebra und Geometrie
Englerstr. 2
D-76131 Karlsruhe

Office hours:
Tu, Th, F 8:30-12:00

Tel.: +49 721 608 47412

Fax.: +49 721 608 46968

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

Lecturer: Prof. Dr. Maria Axenovich, Torsten Ueckerdt
Classes: Seminar (0121300)
Weekly hours: 2

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
Lecturer Prof. Dr. Maria Axenovich
Office hours: Mon. 13:00-14:00
Room 1.043 Kollegiengebäude Mathematik (20.30)
Email: maria.aksenovich@kit.edu
Lecturer Torsten Ueckerdt
Office hours:
Room Kollegiengebäude Mathematik (20.30)
Email: torsten.ueckerdt@kit.edu


  • 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