Algorithme de coloration de graphe

- Principe de l'algorithme:

     L’algorithme de Widgerson est un algorithme de coloration assez spécial, car il n’est applicable que pour les graphes où 3 couleurs sont nécessaires. De plus, il fait appel à deux autres algorithmes de la coloration de graphe. Cet algorithme consiste à trouver tous les sommets avec au moins  voisins non coloriés, où n est égal au nombre de sommets du graphe. On applique à ces sommets l’algorithme de ‘2-coloriage’. On va donc utiliser deux couleurs différentes, pour colorier les voisins de ces sommets. Une fois cette étape réalisée, on applique l’algorithme glouton aux sommets restants.

- Analyse de l'algorithme:

     L’algorithme Widgerson ne s’applique que pour les algorithmes 3-coloriables. Pour utiliser cet algorithme il faut donc s’assurer préalablement que le graphe à colorier rempli cette condition. Ensuite, il nécessite la connaissance des algorithmes glouton et 2-coloriage, ce qui peut rendre son exécution plus compliquée.