Cycles of relatively prime length and the road coloring problem (Q5939288)

A directed graph \(G=(V,E)\) is given in such a way that each outdegree is \(k\). We label each edge of \(G\) with one of \(k\) labels in such a way that for each vertex \(v\) and each label \(l\) there is a unique edge \(e\) leaving \(v\) and having label \(l\). Such a labeling is said to be a synchronizing coloring of \(G\) if there is a certain sequence \((l_1,l_2,\ldots,l_m)\) of labels, so that for any vertex \(v\) of \(G\) the walk that starts from \(v\) and follows the edges labeled with \(l_1,l_2,\ldots,l_m\) always ends at the very same vertex \(w\) of \(G\), independently of \(v\). The road coloring problem is to find a synchronizing coloring for a given graph \(G\) as above. Clearly, a synchronizing coloring cannot exist if \(G\) is periodic, that is \(V\) can be partitioned into parts \(V_1,V_2,\ldots,V_p\) so that each edge goes from some \(V_i\) to the next part \(V_{i+1}\) (addition is modulo \(p\)). It is generally believed that for any aperiodic graph (a graph that is not periodic, or in other words, a graph that contains some directed cycles that have relatively prime length) there always exists some synchronizing coloring. The paper justifies this belief for certain classes of graphs. The basic idea is to find label-sequences for a given labeling that ensure that the corresponding path ends on a certain cycle. As a corollary a related earlier result of \textit{N. Jonoska} and \textit{S. Suen} [Monocyclic decomposition of graphs and the road coloring problem, Congr. Numerantium 110, 201-209 (1995; Zbl 0905.05066)] is deduced. The proof of the most general condition involves some number theory, namely the Chinese remainder theorem.