Résumé:
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.
