Nombre chromatique et nombre chromatique équitable d'un graphe.

Abstract

Dans ce mémoire, nous avons étudié les nombres chromatique et chromatique équitable d'un graphe. Après avoir donné les concepts de base de la théorie des graphes, des définitions et motivations ainsi que des propriétés de ces nombres ont été présenté. Une introduction sur la théorie de la complexité est aussi présentée dans ce travail. Un état de l'art de quelques cas polynomiaux est reporté. Nous avons ensuite étudié ces nombre pour quelques graphes particuliers. Comme ces problèmes sont NP-difficiles, nous avons présenté des algorithmes d'approximation et des bornes inférieures et supérieures pour la résolution de ces problèmes.