title: Algorithme de Wigderson
text: # Algorithme de Wigderson
  
  L'algorithme de Wigderson est un algorithme de coloration de graphe. C'est un algorithme de complexité en temps polynomiale, qui colore avec $O({\sqrt {n}})$ couleurs les graphes 3-coloriables. Il est dû à Avi Wigderson.
  
  ## Description
  
  Cet algorithme s'effectue sur des graphes qu'on sait 3-coloriables. Soit $G=(S,A)$ un tel graphe. On note $n$ le nombre de sommets de $G.$
  
  * On prend comme couleur initiale $c=0.$
  * Pour tout $s\in S$ non déjà colorié et avec au moins ${\sqrt {n}}$ voisins non coloriés : on considère le sous graphe induit par l'ensemble des voisins de $s$ pas encore coloriés, et on le 2-colorie avec les couleurs $c$ et $c+1.$ On ajoute à $c$ le nombre de couleurs utilisées.
  * Avec l'algorithme glouton, on colorie le reste des sommets avec des couleurs plus grandes que $c.$
  
  La complexité de l'algorithme de Wigderson est polynomiale en $n$ et détermine un coloriage de $G$ qui utilise $O({\sqrt {n}})$ couleurs.
  
  ## Correction de l'algorithme de Wigderson
  
  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 $m$ le nombre de sommets traités durant le point 2, alors l'algorithme colorie au moins $m{\sqrt {n}}$ sommets. On a donc :
  
  $m{\sqrt {n}}\leq n$, i.e $m\leq {\sqrt {n}}$.
  
  Ainsi le nombre de couleurs utilisées dans le point 2 est d'au plus $2{\sqrt {n}}$. Ensuite, le degré du sous-graphe induit par les sommets non coloriés à la fin du point 2 est inférieur ou égal à ${\sqrt {n}}-1$. L'algorithme glouton utilise donc au plus ${\sqrt {n}}$ couleurs pour colorier le reste des sommets. Ainsi, le nombre de couleurs utilisées est d'au plus $3{\sqrt {n}}$, il est donc en $O({\sqrt {n}})$.
  
  ## Exemple
  
  Le graphe suivant est 3-coloriable :
  
  ### Application de l'étape 2
  
  Le sommet $4$ 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 $6$.
  
  Après ces opérations, il n'y a plus de sommet non colorié avec au moins ${\sqrt {12}}$ voisins non coloriés.
  
  ### Application de l'étape 3
  
  On applique l'algorithme glouton aux sommets restants.
  
  ## Histoire
  
  L'algorithme a été publié en 1983 par Avi Wigderson.
  
  