Nombre chromatique
Nombre minimum de couleurs différentes nécessaires pour colorier tous les
sommets d'un graphe de façon à ce que deux sommets adjacents aient des couleurs différentes.
Les premiers résultats de coloration de graphe concernent presque exclusivement les graphes planaires : il s'agit alors de colorier des cartes. Des mathématiciens ont démontré, dès la fin du 19e siècle, qu'il suffisait de 4 couleurs pour colorier une carte géographique
Exemple
Le nombre chromatique des graphes ci-dessous est 3 :
