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.