L’algorithme de Powell – Welsh
Dans la liste des sommets, colorer avec la couleur courante tous les sommets non colorés et non adjacents à aucun sommet déjà coloré avec la couleur courante.
4
Si tous les sommets ne sont pas colorés, revenir à l’étape 2.
5
Chercher dans la liste des sommets le premier sommet non coloré et le colorer avec la couleur courante.
3
Choisir une nouvelle couleur dite « courante ».
2
Numéroter les sommets dans l’ordre des degrés décroissants.
1
3
4
3
4
4
5
4
5
H
G
F
E
D
C
B
A
A C B D E G F H
A
H
B
E
C
G
F
D