chromatique [grec : khrôma, couleur] (T) :

Graphe k-chromatique

Soit k un entier naturel et K={1,2,...,k}.

Un graphe est k-chromatique si et seulement si il existe une fonction c de G dans K de sorte que deux sommets adjacents distincts n'aient pas la même image.
Intuitivement, cela signifie qu'il est possible de colorier les sommets à l'aide de k couleurs de sorte que deux sommets adjacents distincts ne soient jamais de la même couleur.

Nombre chromatique d'un graphe

Plus petit entier k tel que ce graphe soit k-chromatique.