Définition
- Colorer un graphe consiste à affecter une couleur à chacun des sommets de sorte que deux sommets adjacents ne portent pas la même couleur.
- On apppelle \textbf{nombre chromatique d’un graphe} le plus petit nombre de couleurs permettant de le colorer.
Comment Encadrer le nombre chromatique d’un graphe
Soit 
l’ordre du plus grand sous-graphe complet de ce graphe .
Soit 
le plus grand degrè de tous les degrès des sommets du graphe. Alors on a toujours :
Où 
est le nombre chromatique du graphe.
Algorithme de coloration
On procède comme suit :
- On range les sommets du graphe dans l’ordre décroissant de leur degrè.
- On donne une couleur au sommet de plus haut degrè et on donne la même couleurs à tous ceux qui ne lui sont pas adjacents.
- On reorganise les sommets restant et on applique encore le processus en changeant de couleur; ceci jusqu’à ce que tous les sommets ont une couleur.
pas adjacents.
