Schedule

Day 1: February 24, 2025

Lecture 1: 2 hrs: FF

Introduction and motivation, basics of graph theory, k-trees, treewidth, equivalence treewidth k/ partial k-trees, basic properties.

Tutorial 1: 2 hrs: FF

Problem solving session with examples: tree decompositions.

Day 2: February 25, 2025

Lecture 2 : 2 hrs: FF

Dynamic programming for trees and graphs of bounded treewidth.

Tutorial 2: 2 hrs: FF

Problem solving session with examples: dynamic programming on tree-decompositions.

Lecture 3: 2 hrs: FF

Brambles and duality theorem for treewidth, relation with cops and robber game.

Day 3: February 26, 2025

Tutorial 3: 2 hrs: FF

Problem solving session with examples: brambles and tree decompositions, relation with cops and robber game. Computing tree-decompositions, nice tree-decompositions, Courcelles’s theorem, related parameters

Lecture 4: 2 hrs: SS

Planar graphs: Euler's formula, number of edges and degeneracy, coloring planar graphs.

Tutorial 4: 2 hrs: SS

Problem solving session with examples: planar graphs, coloring.

Day 4: February 27, 2025

Lecture 5 : 2 hrs: SS

Five color theorem, discharging method, potential method for planar graphs.

Tutorial 5: 2 hrs: SS

Problem solving session with examples: discharging method, potential method for planar graphs.

Lecture 6 : 2 hrs: FF

Treewidth of planar graphs. Application to FPT algorithms and approximation algorithms, extension to bounded local treewidth.

Day 5: February 28, 2025

Tutorial 6: 2 hrs: FF

Problem solving session with examples: treewidth of planar graphs.

Lecture 7 : 2 hrs: SS

Subdivisions and minors, Kuratowski/Wagner theorems, planarity testing, minor-closed graph classes.

Tutorial 7: 2 hrs: SS

Problem solving session with examples: subdivisions and minors.

Day 6: March 3, 2025

Lecture 8: 2 hrs: SS

Shallow minors, greatest reduced average degree, graph classes of bounded expansion.

Tutorial 8 : 2 hrs: SS

Problem solving session with examples: Shallow minors and graph classes of bounded expansion.

Day 7: March 4, 2025

Lecture 9: 2 hrs: FF

Generalized coloring numbers, algorithmic applications.

Tutorial 9 : 2 hrs: FF

Problem solving session with examples: Generalized coloring numbers.

Lecture 10: 2 hrs: FF

Neighborhood complexity, VC-dimension, applications to locating-dominating sets and metric dimension.

Day 8: March 5, 2025

Tutorial 10: 2 hrs: FF

Problem solving session with examples: neighborhood complexity and VC-dimension.

Lecture 11 : 2 hrs: FF

Low tree-depth colorings and applications to FPT algorithms.

Tutorial 11: 2 hrs: FF

Doubts clearing session

Day 9: March 6, 2025

Lecture 12 : 2 hrs: FF

Approximation for distance-d independent set and dominating set, FO model checking, nowhere dense graphs, structured dense graph classes (clique-width, twin-width, flip-width...), conclusion

Tutorial 12: 2 hrs: FF

Doubts clearing session