Monsieur A donne rendez-vous à ses amis: B, C , D et E.
Pour cela il a peint les routes en rouge et bleu comme indiqué, et
a dit à chacun: "Prends la route Bleu, puis de nouveau la Bleu,
la Rouge, encore la Rouge, la Bleu puis finalement la Rouge et
tu seras arrivé."On peut vérifier que chacun, suivant l'instruction donnée par Monsieur A arrive bien à bon port.
Plus formellement, étant donné un graphe orienté D de degré sortant constant 2, une bonne coloration des arcs de D est une coloration de ses arcs en 2 couleurs : rouge (noté R) et bleu (noté B) telle que chaque sommet soit début d'un arc rouge et d'un arc bleu. On considère des mots sur les deux lettres R et B. Appliquer un mot w sur un sommet x du digraphe revient à se placer sur x et à suivre lettre après lettre les arcs dont la couleur correspond à la lettre courrante. Le sommet d'arrivée est appelé image de x par w. Dans l'exemple précédent, on a appliqué le mot BBRRBR à chacun des sommets. Appliquer un mot w à un ensemble de sommets X revient à appliquer w à chacun des sommets de X. L'ensemble des images de ces sommets est appelé image de X par w. Enfin, un mot w est dit contractant, si l'image de V, ensemble de tous les sommets du graphe, par w est constitué d'un seul sommet (ce qui est le cas sur l'exemple précédent).
La Conjecture du Problème de "Road Coloring" affirme que, à une famille d'exceptions près, quelsoit le digraphe D choisi au départ avec degré sortant constant, D admet toujours une bonne coloration de ses arcs qui possède un mot contractant.
Cette Conjecture est ouverte depuis 1970. Elle est résolue dans le cas où D possède un circuit de longueur un entier premier (O'Brien, 1981) et aussi dans le cas où D est eulérien (Kari 2001).
Durant cet atelier de travail, nous présenterons le problème, proposerons quelques exemples de recherche de mots contractants sur des exemples simples et exposerons la famille d'exceptions à l'exposé de la conjecture. Si le temps le permet, nous présenterons aussi les idées de preuve des cas connus et des pistes de recherche evisagées pour quelques cas particuliers toujours ouverts.