L'algorithme de Wigderson est un algorithme de coloration de graphe. C'est un algorithme de complexité en temps polynomiale, qui colore avec couleurs les graphes 3-coloriables. Il est dû à Avi Wigderson.
Cet algorithme s'effectue sur des graphes qu'on sait 3-coloriables. Soit un tel graphe. On note le nombre de sommets de
La complexité de l'algorithme de Wigderson est polynomiale en et détermine un coloriage de qui utilise couleurs.
L'algorithme de Wigderson renvoie bien un coloriage, car l'algorithme glouton et l'algorithme de 2-coloriage sont corrects, et que les sous-graphes considérés dans l'algorithme sont coloriés avec des ensembles de couleur disjoints.
Si on note le nombre de sommets traités durant le point 2, alors l'algorithme colorie au moins sommets. On a donc :
, i.e .
Ainsi le nombre de couleurs utilisées dans le point 2 est d'au plus . Ensuite, le degré du sous-graphe induit par les sommets non coloriés à la fin du point 2 est inférieur ou égal à . L'algorithme glouton utilise donc au plus couleurs pour colorier le reste des sommets. Ainsi, le nombre de couleurs utilisées est d'au plus , il est donc en .
Le graphe suivant est 3-coloriable :
Le sommet a 4 voisins non coloriés : on les 2-colorie, puis on fait de même pour les 4 voisins non coloriés du sommet .
Après ces opérations, il n'y a plus de sommet non colorié avec au moins voisins non coloriés.
On applique l'algorithme glouton aux sommets restants.
L'algorithme a été publié en 1983 par Avi Wigderson[1].