nombre chromatique

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 :
nombre_chromatique


Essayez des activités de Netmath gratuitement

et voyez comment elles peuvent vous aider.