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. On désigne par !(G) et (G) respectivement la taille d.une clique maximum de G et la taille d.un couplage maximum de G. Parmi les nombreux paramètres de coloration existants, on a étudié un nouveau concept de coloration des sommets, appelé coloration dominante ou b..coloration. La coloration propre des sommets est une attribution de couleurs aux sommets de G de telle sorte que deux sommets adjacents aient toujours des couleurs di¤érentes. Le nombre chromatique, noté (G); est le nombre minimum de couleurs pour lequel G admet une coloration propre. 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. Une k..coloration de Grundy d.un graphe G est une coloration propre utilisant k couleurs véri.ant la propriété suivante : chaque sommet v, coloré par une couleur i ; 1 i k; doit être adjacent à au moins i..1 sommets colorés par chacune des couleurs j telles que 1 j i .. 1: Le nombre de Grundy d.un graphe G, noté (G); est le nombre maximum de couleurs nécessaires pour une coloration de Grundy de G. Dans ce mémoire, on présente deux nouvelles bornes pour le nombre b..chromatique en fonction de n; ! et : On caractérise par la suite les graphes bipartis dont le nombre b(G) = n=2 ou (n+1)=2 et les graphes tels que b(G).. (G) = n=2 ou (n..1)=2: On détermine la valeur exacte du nombre b..chromatique du produit croisé de certains arbres particuliers, on montre aussi que ces graphes sont b..continus. Un graphe G est dit b..continu s.il admet une b..coloration avev k couleurs pour tout k, (G) k b(G): Après avoir remarquer que les deux paramètres b(G) et (G) sont en général incomparables, on montre que, si G est sans P4 alors b(G) (G). On montre aussi que le paramètre b(G) peut être calculé en temps polynomial dans cette classe de graphes. En.n, on établit un théorème qui caractérise les graphes tels que b(H) = (H) pour tout sous graphe induit H de G.