Un exemple où l’algorithme de Powel-Welsh donne systématiquement un nombre de couleurs supérieur au nombre chromatique…
2
H
2
3
4
4
4
4
5
D
F
G
E
B
A
C
Si on suit l'algorithme de P-W, on colorie d'abord C qui a le degré le plus élevé puis dans la même couleur G qui est le seul sommet de degré 4 non adjacent à C. La couleur ne peut plus être réutilisée car les autres sommets sont tous adjacents soit à C soit à G.
A
E
H
B
C
F
G
D