Etude de la b-coloration dans les graphes

Abstract

Le travail de cette thèse porte sur l’étude de la b-coloration dans les graphes. Etant donné un graphe G = (V; E), une coloration propre de sommets de G est une affectation de couleurs aux sommets de sorte que deux sommets adjacents aient des couleurs différentes. Le nombre minimum de couleurs nécessaires à la coloration des sommets de G est appelé le nombre chromatique de G et noté ¬(G): Une b-coloration d’un graphe G est une coloration propre de sommets de G telle que chaque classe de couleur contient au moins un sommet qui est adjacent à au moins un sommet de chaque classe de couleur autre que la sienne. Le nombre b-chromatique b(G) d’un graphe G est le plus grand entier k tel que G admet une b-coloration avec k couleurs. Cette thèse comporte trois parties. Dans la première partie, on présente une borne supérieure pour le nombre b-chromatique b(G) en fonction de l’ordre n et la taille d’une clique maximum !(G) d’un graphe G et on caractérise les graphes bipartis atteignant cette borne. On discute la relation entre b(G) et ¬(G) ensuite on déduit un autre résultat concernant la relation entre b(G v) et b(G) o˘ G v est le graphe obtenu à partir de G en supprimant le sommet v de G et toutes les arêtes incidentes à v: Dans la deuxième partie, on donne des bornes et des valeurs exactes du nombre b-chromatique de certains graphes particuliers, à savoir les graphes de Harary Hk; n d’ordre n lorsque k est pair, le graphe milieu et le graphe total d’une chacune Pn, d’un cycle Cn; d’une roue Wn et d’une couronne d’une chacune Cr(Pn). La troisième partie est consacrée à l’étude des graphes dits b-critiques et arêtes b-critiques, c’est à dire les graphes G dont le nombre b-chromatique diminue lorsque G est modifié en supprimant un sommet ou une arête quelconque de G. Dans ce sens, on donne une caractérisation des graphes P4-sparses arête b-critique, quasi adjoints arête b-critiques et des arbres b-critique