Sous-Quorum-Coloration de quelques classes d'arbres

Abstract

Une partition π = {V 1 , V 2 , ..., V k } de l’ensemble des sommets V d’un graphe G en k classes V , avec i ∈ {1, ..., k}, est une quorum-coloration de G si pour tout sommet v ∈ V, au moins la moitié des sommets du voisinage fermé N i [v] de v a la même couleur que v. La cardinalité maximum d’une quorum-coloration de G est le nombre de quorum-coloration de G noté ψ q G (G). Une sous-quorum-coloration de G est une quorum-coloration d’un sousgraphe de G induit par une partie S de V. Le nombre de sous-quorum-coloration de G est égal au cardinal maximum d’une sous-quorum-coloration de G et est noté par ψ (G). Dans ce mémoire, nous déterminons la valeur exacte du nombre de sous-quorum-coloration pour quelques familles infinies d’arbres. sq