Let G be a finite directed graph where all the vertices have the same out-degree k. Let A be the alphabet containing the letters 1, ..., k. A synchronizing coloring (also known as a collapsible coloring) in G is a labeling of the edges in G with letters from A such that (1) each vertex has exactly one outgoing edge with a given label and (2) for every vertex v in the graph, there exists a word w over A such that all paths in G corresponding to w terminate at v.
The terminology synchronizing coloring is due to the relation between this notion and that of a synchronizing word in finite automata theory.
For such a coloring to exist at all, it is necessary that G be both strongly connected and aperiodic.[4] The road coloring problem states that these two conditions are also sufficient for such a coloring to exist. Therefore, the road coloring problem can be stated briefly as:
Every finite strongly-connected aperiodic directed graph of uniform out-degree has a synchronizing coloring.
刚看新闻说“线路着色谜题”被解了，但由于书读的少不知道什么是线路着色谜题，所以想找来看看，baidu百科没有词条。wiki中文又没开放，实在找不到。万能的TG，给偶一个解吧。
