Autour de l’algorithme de P - W
L’algorithme de coloriage de Powell-Welsh encore appelé algorithme « glouton » ne conduit pas toujours à un coloriage optimal, c’est à dire utilisant un nombre de couleurs égal au nombre chromatique du graphe….
Tous les sommets de ce graphe sont de degré 2
Une couleur ne suffit pas pour colorer le graphe puisque A et E sont adjacents,
Mais 2 couleurs suffisent…
A
B
C
D
E
F