Un exemple où l’algorithme de Powel-Welsh donne |
systématiquement un nombre de couleurs supérieur au
nombre chromatique… |
G
H
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. |
F
E
A
D
B
C
C
A
B
E
G
F
D
H
5
4
4
4
4
3
2
2