nombre chromatique d’un graphe

COMBINATOIRE

La coloration d’un graphe est une notion de théorie des graphes qui consiste à attribuer une couleur à chacun de sommets du graphe de sorte que deux sommets reliés par une arête soient de couleur différente.
Elle n’est définie que pour les graphes simples sans boucles et sans arêtes multiples.
Le nombre chromatique est le plus petit nombre de couleurs nécessaires pour colorier le graphe.
Le théorème de Brooks donne une relation entre le degré maximal d’un graphe et son nombre chromatique.