ECTS : 3
Description du contenu de l'enseignement :
Le but de ce cours est de présenter plusieurs classes de graphes bien connus et de les étudier d’un point de vue structurel (théorème de caractérisation) et algorithmique.
On étudiera entre autres les classes de graphes suivants :
Graphes d’intervalles
Graphes triangulés
Graphes de permutation
Graphes de comparabilité
Graphes planaires
Graphes de largeur d’arbre bornée
Graphes parfaits
En ce qui concerne l’aspect structurel, on présentera les notions suivantes : sommet simplicial, séparateur, schéma d’élimination, triple astéroïdal, mineur, largeur d’arbre, largeur de clique, graphes d’intersection, orientation transitive, caractérisation par sous-graphes induits interdits, décomposition arborescente, k-arbre partiel, … Pour l’aspect algorithmique, on envisage d’étudier entre autres les problèmes suivants : problème de reconnaissance de ces classes de graphes, problème de coloration, problème de la clique maximum, problème du stable maximum, problème du voyageur de commerce, etc.
Bibliographie, lectures recommandées :
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.