Contribution à l'étude de la b-coloration dans les graphes.

Abstract

Soit G = (V, E) un graphe simple d'ordre n où V est l'ensemble des sommets et E l'ensemble des arêtes. Parmi les nombreux paramètres de coloration existants, on s'intéresse à l'étude d'un nouveau concept de coloration des sommets, appelé coloration dominante ou b-coloration. La coloration dominante est une coloration propre telle que toute classe de couleur contient un sommet adjacent à au moins un sommet de chaque classe de couleur autre que la sienne. Le nombre b-chromatique, noté b(G), est le nombre maximum de classes de couleurs dans une coloration dominante. Dans ce mémoire, on détermine le nombre b-chromatique du graphe milieu de certains graphes, on donne le nombre b-chromatique du graphe de Halin en utilisant l'algorithme de Irving et Manlove pour la coloration des arbres ensuite on adapte les résultats trouvés par Silva et Maffray [9] pour les graphes cactus au graphe milieu du l'arbre binaire. Enfin, on donne le nombre b-chromatique du graphe milieu de la somme cartésienne de deux chaînes.