Structural and algorithmic graph theory

Objectives: In this course, we introduce several well-known graph classes and we study their structural properties (e.g. characterization theorems) as well as their algorithmic properties (e.g. efficient algorithms for some classical optimization problems).

Content: We study among others the following graph classes: interval graphs, chordal graphs, permutation graphs, comparability graphs, planar graphs, bounded treewidth graphs, perfect graphs. Concerning the structural properties, we will introduce for instance the following notions: simplicial vertex, separator, elimination scheme, asteroidal triple, minor, treewidth, cliquewidth, intersection graph, transitive orientation, characterization by a family of forbidden induced subgraphs, tree decomposition, partial k-tree,… . Concerning the algorithmic properties, we will focus on the following classical optimization problems: recognition problem for the graph classes mentioned above, coloring problem, maximum clique problem, maximum stable set problem, travelling salesman problem,… .

Bibliographie

• M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second edition, Academic Press, New York, 2004, Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.

• A. Brandstädt, V. B. Le and J. P. Spinrad Graph Classes: A Survey SIAM Monographs on Discrete Mathematics and Applications, 1999.