Méthode de Welsh Powell pour la coloration de graphe

[road]

Bonjour,

Ma question est simple : généralement pour colorer un graphe j'utilise la méthode de Welsh Powell.
Cependant il parraît que cette méthode propose une coloration non optimale.
J'aimerai bien m'en convaincre, alors je cherche un contre exemple (ie un graphe où Welsh Powell donne un nombre chromatique > (G) ).

Voilà, merci d'avance !

[Ben314]

Salut,
Wiki est ton ami :
Tu trouvera sur la page "Coloriation de Graphes" que :
Remarquons que l'algorithme de Welsh et Powell peut aboutir à la pire des colorations possibles, par exemple si le graphe G a la structure de couronne à n sommets, son nombre chromatique est 2 (si n est pair) tandis que Welsh-Powell donne dans certains cas (selon l'ordre dans lequel sont rangés les sommets) une coloration utilisant n/2 couleurs !

[road]

Salut Ben314,

Merci pour ta réponse ! J'avais lu cette page wikipédia, mais j'ai beau essayé de 'mal' colorier ces graphes en horloge, j'arrive à une coloration à 2 couleurs (en suivant Welsh Powell)...
Pourrais tu essayer de m'expliquer quel problème pourrait survenir s'il te plaît ?

Merci d'avance !

[Ben314]

Si les sommets de ton graphe sont et les (uniques) arrêtes sont les pour et que tu applique Welsh et Powell en prenant comme ordre pour les sommets , ça donne quoi ?