Responsables : Olivier Baudon

Ce cours du S8 vaut 6ECTS.

Partie 1 (Olivier Baudon) :  Coloration de graphes

Cette partie concerne les problèmes de la coloration de graphes, c'est à dire :

- comment colorier les sommets d'un graphe de façon à ce que deux sommets voisins aient toujours des couleurs différentes ;

- comment colorier les arêtes d'un graphe de façon que deux arêtes partageant un sommet aient toujours des couleurs différentes.

Après avoir montré les bornes classiques sur le nombre de couleurs nécessaires, nous nous intéressons plus particulièrement à la classes des graphes parfaits, ce qui nous permet d'aborder des classes de graphes classiques, très souvent utilisées comme exemples pour différents paramètres : graphes d'intervalles, graphes de comparabilité, graphes scindés …

Partie 2 (à compléter) : Programmation Linéaire

Cette partie du cours est consacrée à la programmation linéaire et à son utilisation pour résoudre des problèmes de graphes. Nous présentons l'algorithme du simplexe, la notion de dualité, …, avant de passer à la question de l'utilisation des programmes linéaires pour les graphes, pour lesquels les solutions demandées sont forcément entières.