coloration 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.
Les premiers résultats concernaient les graphes planaires et tout particulièrement le théorème des quatre couleurs .
La notion de coloration 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.