Dans cet exposé, nous cherchons à colorier proprement des graphes de sorte que deux sommets adjacents n'aient pas le même ensemble de couleurs dans leur voisinage fermé. On peut par exemple colorier de cette manière n'importe quel graphe biparti avec 4 couleurs, mais savoir si l'on peut colorier un graphe biparti avec seulement 3 couleurs est NP-complet. Nous nous interesserons aussi à une autre classe de graphes : les graphes triangulés pour lesquels nous pensons que 2*k couleurs sont suffisantes, avec k la taille de la plus grande clique. Enfin, je donnerai des relations avec le nombre chromatique et avec le degre maximum du graphe.