Problème de coloration des sommets d'un graphe

Abstract

Chapitre 1 : Notions de base Les définition de la théorie de graphe nécessaires _a la suite de ce mémoire sont introduite dans se chapitre. Chapitre 2 : Problème de coloration Ce chapitre concerne le problème de coloration en générale, son historique, son utilité, une generalition et définition, l'NP-complétude du problème, quelque notion sur le nombre chromatique, et la coloration des arêtes. Chapitre 3 : Coloration des graphes parfaits Ce chapitre traite la classe des graphes parfaits, des algorithmes permettant de colorier certain type de cette classe en temps poly loyale, et on termine par un exemple. Chapitre 4 : Techniques et algorithmes de coloration Dans ce chapitre on décrit les différentes technique de coloration, et on donne quelque algorithmes de coloration, et on termine par un algorithme récent . Chapitre 5 : Coloration des graphes planaires Ce chapitre traite la classe des graphes planaire, la reconnaissance, le théorème des 4 couleurs, le théorème de 5 couleurs, et algorithme de coloration associe a cette classe de graphes. Chapitre 6 : Implémentation et résultats