**Instructors:**Stéphan Thomassé and Nicolas Trotignon

**Prerequisites:**No specialized knowedge is required, however basic notions in graph theory, algorithms, complexity theory and linear algebra will help.

**Objective:**The two most difficult results in graph theory, i.e. the graph minor theorem and the strong perfect graph theorem were both proved using graph decompositions techniques. This course is aimed to give an overview on these tools.

**Course outline:**

1)**Tree-Width and Graph Minor Theorem**.

Tree-width and related notions

The Robertson and Seymour's graph minor theorem

Graph Searching

Bramble (dual of tree-width)

Courcelle's clique width and Oum's rank width

2)**Applications of tree-width****.**

Dynamic programming

Testing for a minor

Parameterized complexity (and kernalizations)

3)**Perfect Graphs**.

Definition and examples of perfect graphs

Lovasz' Perfect Graph Theorem

Chudnovsky, Robertson, Seymour and Thomas' Strong Perfect Graph Theorem

Algorithmic issues : recognition and coloring

Beyond perfect graphs: chi-boundedness and extended formulations of the stable set polytope

Gyarfas's conjectures

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

**Bibliography:**

R. Downey and M. Fellows,*Parameterized complexity*. Springer 1999.

L. Lovász,*Graph minor theory*. Bull. Amer. Math. Soc. 43(2006), 75-86.

N. Trotignon,*Perfect graphs, a survey*. 2013.