Tous les algorithmes distribués que l’on considèrera dans cette partie seront dans le modèle
LOCAL.
On suppose que le graphe G est un cycle orienté muni d’une m-coloration. Tout sommet u possède une variable c(u) appartenant de 0 a m-1 représentant la couleur du sommet u.
L’orientation est définie en u par les relations prédécesseurs et successeurs, notées respectivement Pred(u) et Succ(u).
Question
Comment on peut montrer qu’en une ronde il est possible de calculer pour G une 4-coloration si m = 6 en donnant l’algorithme correspondant.
Et en déduire qu’il est possible de calculer
une 3-coloration pour G en partie entier de 1/2log*m + 2 rondes
On suppose maintenant que G est un graphe possèdant une 1-orientation, définie par
la relation Père(u) pour tout sommet u, et toujours muni d’une m-coloration.
-----