Etude de la b-coloration et de la b-continuité 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'une partition minimum de l'ensemble des sommets de G en cliques. Une k‐coloration propre d'un graphe G est une partition {V₁,V₂,...,Vk} de V(G) en k stables, appelés classes de couleurs. Le nombre minimum de classes de couleur qui partitionnent l'ensemble V est le nombre chromatique noté χ(G). Une 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. Un graphe G est dit b‐continu s'il admet une b‐coloration avec k couleurs pour tout k, χ(G) ≤ k ≤ b(G). Dans une k‐ coloration un sommet v אVi est appelé sommet de Grundy si v est adjacent à au moins un sommet dans chaque classe de couleur Vj, pour tout j < i. Une k‐coloration partielle de Grundy d'un graphe G est une coloration propre utilisant k couleurs telle que toute classe de couleur Vi, 1 ≤ i ≤ k, contient au moins un sommet de Grundy. Le nombre partiel de Grundy d'un graphe G, noté ∂Γ(G), est le nombre maximum de couleurs nécessaires pour une coloration partielle de Grundy de G. Dans ce mémoire, on présente deux nouvelles bornes pour le nombre b‐chromatique, l'une dans un graphe quelconque en fonction de n, ߱ et ߠ , et l'autre dans la classe des graphes sans K1,t, t ≥3 en fonction de ∆ et t où ∆ est le degré maximum de G. On donne une borne inférieure du nombre b‐chromatique du produit total de deux graphes, et on détermine la valeur exacte du nombre b‐chromatique du produit total de deux graphes particuliers, et on montre que ces graphes sont b‐ continus. On montre aussi que les graphes sans P₄ sont b‐continus, et on présente une autre démonstration de la b‐continuité des arbres. Enfin, on montre que b(G) ≤ ∂Γ(G) pour tout graphe G, et on établit un théorème qui caractérise les graphes tels que b(H)=∂Γ(H) pour tout sous graphe induit H de G.