Coloration d'un graphe et nombre chromatique

On appelle coloration d'un graphe dont l'ensemble des sommets est $V$ toute application $\varphi:E\to\mathbb N$ telle que $\varphi(x)\neq \varphi(y)$ si $x$ et $y$ sont deux sommets adjacents. On parle de coloration car on associe souvent à chaque entier une couleur. Une coloration d'un graphe c'est donc une façon de colorier ce graphe en attribuant une couleur à chaque sommet et de sorte que deux sommets adjacents n'aient pas la même couleur.

On appelle nombre chromatique d'un graphe le plus petit nombre de couleurs pour le colorier. Pour certains problèmes d'optimisation, on cherche à colorier le graphe avec un nombre minimal de couleurs.