ECTS : 3
Volume horaire : 15
Description du contenu de l'enseignement :
In this course, we introduce the notion of perfect graph. We start by proving that bipartite graphs, their line-graphs and the complement of both classes are all perfect. We prove the weak perfect graph theorem, namely, that complement of perfect graphs are perfect. Further problems, around the notion of complete bipartite subraph are studied to illustrate more the interactions between graphs and linear algebra.
Compétence à acquérir :
The goal is to understand the deep links between efficient algorithms, structures in graphs, and geometry of polyhedra.
Mode de contrôle des connaissances :
One exam.
Bibliographie, lectures recommandées :
Bibliographie Combinatorial Optimization : Polyhedra and Efficiency. A. Schrijver , Springer (2003)