Résumé | La coloration est un problème classique de la théorie des graphes et de l'algorithmique distribuée. Dans cet exposé, je ferai un résumé des résultats obtenus récemment pour la résolution de ce problème. On montrera comment obtenir une (Delta+1)-coloration en O(log n) rondes et en utilisant des messages à 1 bit. Nous montrerons que l'algorithme est optimal et ce en utilisant des revêtements de graphes. Dans le cas où le réseau est un anneau, nous verrons qu'en utilisant la transformée de Mellin, il est possible de donner la valeur exacte de la constante cachée dans le O(log n). |