Instructors: Marthe Bonamy and François Dross
Lecture notes: Available here.
Objective:
Many problems can be modelled with graphs. In this course, we will overview various approaches to solve various problems on graphs. While there will be a heavy focus on structure, efficient algorithms will also be integral to the course.
Course outline:
1) Introduction (September 17th).
Linking chromatic number χ with parameters Δ and ω.
Greedy bounds and Brooks' theorem
Reed's conjecture
Mycielski's construction
2)
Probabilistic Method (September 24th).
α and ω: Ramsey's theorem and Gn,p
Gn,p and graphs of large chromatic number and large girth
Colouring sparse graphs with few colours using the Lovasz Local Lemma
Turan's theorem, and the Szemeredi Regularity Lemma
3)
Edge-colouring (October 1st, TBD).
4)
Graph minors and other structures in graphs (October 8th, TBD).
5)
Discharging and Fixed-Parameter Tractability (October 15th, TBD).
6)
Colouring algorithms (October 22nd, TBD).
7)
Treewidth (October 29th, TBD).
8)
Discharging and Fixed-Parameter Tractability, v2 (November 12th, TBD).
9)
Vertex partitions and sparsity (November 19th, TBD).
10)
List colouring (November 26th, TBD).
11)
Graph homomorphism (December 3rd, TBD).
12)
Hardness reductions (December 10th, TBD).
Possible lectures that did not get chosen: (non-exhaustive list).
χ-bounded graph classes
Fractional colouring
Edge decompositions and sparsity
Counting graphs with a given property
Geometric graphs
Validation: There will be a final exam on January 14th from 9am to 10:30am (all notes allowed) and one homework assignment (Deadline: December 17th). For the homework, any delay past December 17th 23:59 CET costs 1 point per day (rounded up). The homework should be emailed to both of us in pdf, either typed or scanned (if scanned, make sure it is legible). It can be either in French or in English. The grade takes into account (with various weights): the file being properly named, the document having a proper title and author, style and orthograph, basic definitions, examples/pictures, main results, example(s) of proof(s), bibliography, global impression. Plagiarizing and other copy/pasting come with a severe penalty.
Bibliography:
R. Diestel, Graph theory. Springer 1996.
M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method. Springer 2002.