Formation liée aux thèmes de recherche des membres de laboratoire ou de l’Equipe

a) Thèse de Doctorat
Num :1	Nom & Prénom du doctorant	Aioula Soumia
	Date et lieu de soutenance	02/02/2022 à Médéa
	Rapporteur	Ikhlef Eschouf Noureddine
	Intitulé du titre du doctorat	Contribution à l’étude des problèmes de la coloration dominante dans les graphes
	URL résumé ou version pdf	Les travaux réalisés dans cette thèse portent sur l’étude de la coloration dominante dans les graphes. Etant donné un graph G = (V, E), une coloration dominante de G est une coloration propre telle que chaque sommet voit (domine) au moins une classe de couleur. Le nombre chromatique dominant, noté χd(G), est le plus petit entier k tel que G admet une coloration dominante avec k couleurs. Dans la première partie de cette thèse, nous déterminons la valeur exacte du nombre chromatique dominant d’une sous classe des forêts dite forêts de chenilles généralisées. Dans la deuxième partie, nous introduisons la notion des graphes arêtes χ + d -critiques, c’est-à-dire les graphes dont la surpression d’une arête quelconque du graphe fait augmenter son nombre chromatique dominant. Dans ce contexte, nous montrons que le nombre chromatique dominant d’un graphe G privé d’une arête quelconque peut augmenter ou diminuer par au plus une unité. Ensuite, nous caractérisons les forêts et les graphes sans P4 qui sont arête χ + d -critiques.

Num :2	Nom & Prénom du doctorant	Bendali-Braham Amel
	Date et lieu de soutenance	03/07/2018 à Médéa
	Rapporteur	Blidia Mustapha
	Intitulé du titre du doctorat	Etude des b-(sommet ou arête)-colorations dans les graphes et leurs comportements vis-à-vis de certaines opérations
	URL résumé ou version pdf	Dans cette thèse, nous nous intéressons essentiellement à la notion de b-coloration dans les graphes. Soit G = (V,E) un graphe. Une b– coloration des sommets (resp., d’arêtes) est une coloration propre de sommets (resp., arêtes) de G telle que chaque classe de couleur possède au moins un sommet (resp. une arête) adjacent (e) à au moins un sommet (resp., une arête) dans chaque classe de couleur autre que la sienne. Le nombre b-chromatique (resp., l’indice bchromatique), noté b (G) (resp., b0(G)) est le nombre maximum de couleurs pour lequel le graphe G admet une b-coloration des sommets (resp., arêtes). Dans la première partie de cette thèse, nous nous intéressons à la b-coloration des sommets d’un graphe. Tout d’abord, nous caractérisons tous les graphes dont la suppression d’une arête quelconque fait diminuer le nombre b– chromatique, un tel graphe est dit arête b-critique. Ensuite, nous donnons une caractérisation des arbres dits be-critiques, c’est-à- dire les arbres dont la contraction d’une arête quelconque fait diminuer leur nombre b-chromatique. Enfin, nous déterminons la valeur exacte du nombre b-chromatique du prisme complémentaire de certains graphes, ainsi nous donnons une borne supérieure de ce paramètre et une caractérisation du prisme complémentaire des graphes sans triangle dont cette borne est atteinte. Dans la deuxième partie, nous nous intéressons à la b-coloration des arêtes, où nous donnons la valeur exacte de l’indice b-chromatique de certains graphes particuliers.