QUORUM-COLORATION OPTIMALE EN TEMPS LINEAIRE POUR LES ARBRES PARFAITS DONT LES SOMMETS DE MEME PROFONDEUR ONT MEME DEGRE

Abstract

Une partition = {V1, V2, ..., Ve} de l'ensemble des sommets V d'un graphe G en classes de couleurs V1, avec 1 ≤ i ≤k, est appelée quorum-coloration si pour tout sommet v € V, au moins la moitié des sommets du voisinage fermé N[v] de vont la même couleur que v. La cardinalité maximum d'une quorum-coloration de G est appelée nombre de quorum-coloration de G et est notée par (G). Une quorum-coloration de cardinalité (G) est une coloration de G. La détermination du nombre de quorum-coloration ou la conception d'un algorithme linéaire le calculant dans un arbre N-aire parfait a été posée récemment comme problème ouvert par Sahbi [25]. Dans ce mémoire, nous résolvons ce problème en concevant un algorithme linéaire trouvant une coloration mais aussi le nombre de quorum-coloration de n'importe quel arbre parfait dont les sommets de même profondeur ont le même degré.