**Instructors:**Marthe Bonamy and StÃ©phan ThomassÃ©

**Prerequisites:**Basic notions in graph theory.

**Objective:**Graph coloring is one of the most studied and least understood concepts in graph theory. This course aims to consider the structure of graphs of high chromatic number and to present a broad overview of the proof techniques in the field.

**Course outline:**

1)**χ, Δ and ω**.

Greedy bounds and Brooks' theorem

Reed's conjecture

Coloring sparse graphs: the probabilistic method

Mycielski's construction

Beyond Mycielski's construction with the probabilistic method

2)**χ-bounded graph classes****.**

Perfect graphs

Decomposition theorems

Graphs with forbidden induced subgraphs

The dream of polynomial χ-boundedness

3)**Generic tools**.

The combinatorial Nustellensatz and polynomial methods

Kernels and Galvin's theorem

Kneser graphs and topological arguments

Planar graphs and the discharging method

**Validation:**There will be a written final exam and a homework assignment.

**Bibliography:**

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