Etude de la b-coloration et la b-continuité dans les graphes

Abstract

Dans cette thèse, nous nous intéressons principalement à la notion de b-coloration dans les graphes et plus particulièrement dans les graphes réguliers. Une classe de couleur est un ensemble de sommets stable coloré avec la même couleur et le minimum de classes de couleurs qui partitionnent l’ensemble des sommets est le nombre chromatique. De nombreux paramètres de coloration propre sont dérivés du nombre chromatique. La plupart de ces paramètres minimisent le nombre de couleurs. D’autres paramètres cherchent à maximiser le nombre de couleurs, on cite entre autres le nombre a-chromatique et le nombre b-chromatique. Dans un premier temps, on s’intéresse aux travaux de certains chercheurs concernant la b-coloration où on cite les résultats essentiels; en particulier ceux de Klavzar & Jakovac et El Sahili & Kouider où on donne une nouvelle preuve simple a leurs théorèmes. Nous avons abordé la conjecture d’El Sahili & M. Kouider à laquelle on donne un contre exemple, on la reformule et on la démontre dans le cas des graphes d-réguliers de petits degrés. Dans un second temps, on a montré la b-continuité des graphes cactus. Finalement, on s’intéresse au nombre b-chromatique dans les graphes de Harary réguliers, où on donne des bornes et des valeurs exactes pour ce paramètre. Enfin on donne les valeurs exactes du nombre b-chromatique, b’-chromatique et bt-chromatique dans le cas des graphes spider (araignée) complets.