Coloration d'un graphe

Colorier un graphe c'est colorier les sommets de telle façon que deux sommets distincts et adjacents aient toujours des couleurs différentes.
Le nombre chromatique est le plus petit nombre de couleurs nécessaires pour colorier le graphe.

Mathématiquement, c'est
1) donner un ensemble {1, 2, 3, 4, ..., n} de couleurs
2) une application surjective f de l'ensemble X des sommets vers l'ensemble des couleurs telle que pour tout arc ou arête (a, b) du graphe, f(a) soit différent de f(b), lorsque a différent de b.
Le nombre de couleurs est n.
Le nombre chromatique du graphe est la plus petit nombre possible de couleurs.


Il est facile de voir :

Si un graphe a n sommets, son nombre chromatique est inférieur ou égal à n.
(On peut donner des couleurs différentes aux sommets).


Si un graphe de n sommets est complet, alors son nombre chromatique est n.
(Deux sommets distincts devront avoir des couleurs différentes, il faut donc au moins n couleurs).

Si le plus grand degré d'un sommet est d, le nombre chromatique est inférieur ou égal à d+1.
(Prendre un sommet de degré d ainsi que les sommets qui lui sont reliés, colorier ces d+1 sommets avec d+1 couleurs différentes. Prendre ensuite, l'un après l'autre, les sommets restants ... pour chacun d'eux, l'une des couleurs, au moins, convient).

(Et donc si un graphe de n sommets a un sous-graphe complet de m sommets, alors son nombre chromatique est compris entre m et n).

Les couleurs sont numérotées 1, 2, 3 ... (Les couleurs sont les naturels non nuls).

1) Dresser une liste des sommets (généralement dans un ordre décroissant des degrés).
2) Tant que tous les sommets ne sont pas coloriés :
Choisir le premier sommet non encore colorié de la liste et lui affecter la plus petite couleur possible, (non déjà affectée à un sommet adjacent).

Remarque : En modifiant l'ordre des sommets de la liste, on peut parfois obtenir un nombre moindre de couleurs.
Cocher l'une des trois options définissant les constructions différentes de la liste des sommets.

Connaissant seulement les degrés des sommets, on peut obtenir une majoration du nbre chromatique :

     
          *  liste ordonnée l = 1 2 .. n  des sommets, (nombre de sommets n)
          *  c(i-1) nb couleurs déjà utilisées avant le sommet i
	  *  d(i) plus grand degré des sommets à partir de i
          *  nb chromatique C
	  
          pour i parcourant la liste des sommets de 1 à n
	       C <= max(c(i-1), 1+d(i))    

En plaçant en début de liste les sommets dont les degrés sont les plus grands, on peut minimiser la majoration

Sommets i 1 2 3 4 5 6 Degrés d(i) 5 5 4 4 3 3 Utilisées c(i) 1 2 3 4 4 4 Espéré C 6 6 5 5 4 4

Au cours de la recherche d'une coloration, en parcourant la liste des sommets, le nombre k de couleurs qui seront nécessaires est compris entre le nombre de couleurs utilisées et le plus grand degré +1 des sommets restant à colorier, ce qui permet de voir l'intérêt du classement dans l'ordre décroissant des degrés.
Lorsque le graphe est planaire, le nombre chromatique est inférieur ou égal à 4, c'est le cas de l'exemple ci-dessus.

Cliquez sur les images pour effectuer les calculs et déterminer des colorations.
Vous pouvez aussi modifier les données pour les adapter à d'autres exemples et chercher une coloration du graphe correspondant.