Coloration

Soit $G = (S, A)$ un graphe non orienté, une $k$-coloration $c$ de $g$ est une application de $S$ dans un ensemble $E$ tel que $\vert E\vert = k$ vérifiant

$$\forall (e, e^\prime) \in A, c(e) \not = c(e^\prime)$$

Le problème de la $k$-coloration est défini comme suit :

• données : un graphe $G$
• question : trouver une $k$-coloration de $G$.

Ce problème est NP-Complet.

Le nombre chromatique $\chi_G$ d'un graphe est la plus petite coloration de ce graphe. Autrement dit,

$$\chi_G = \min\{k \vert G\ est\ k-colorable\}$$

• données : un graphe $G$
• question : trouver le nombre chromatique de $G$.

Ce problème est aussi NP-Complet.