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.
1) Tree-Width and Graph Minor Theorem.
Tree-width and related notions
The Robertson and Seymour's graph minor theorem
Bramble (dual of tree-width)
Courcelle's clique width and Oum's rank width
2) Applications of tree-width.
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
Validation: There will be a written final exam and a homework assignment.
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.