• 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.

Options for the homework (8 pages on one of those topics -- two students can pick the same topic but no three students can. Email both of us asap with your choice, and let us know if you would like an option not listed):

Cographs and their many characterizations

Twinwidth

Dichromatic number

Even-hole-free graphs

Jones' conjecture and/or the Erdos-Posa property

Cops and robbers

Kempe changes

α(Gn,p) when p=f(n)

Queue number and/or stack number

Planar graphs as intersection of shapes in the plane

• Bibliography:

R. Diestel, Graph theory. Springer 1996.

M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method. Springer 2002.