论文标题
关于概括道路定理的猜想的注释
A note on conjectures generalizing the road colouring theorem
论文作者
论文摘要
道路着色定理以恒定的超级距离构成了牢固连接的有向图的类别，这些图形承认了同步的道路着色。本文的主题是一对相关的猜想，将道路彩色定理推广到具有非恒定级别的图形；我们给出理由相信这两个猜想都是真实的。我们的主要结果集中在两类图上，证明了一类图形的猜想，也证明了另一类图形的猜想之一。我们还提出了计算机模拟，以提供一些猜想的经验证据。
The road colouring theorem characterizes the class of strongly connected directed graphs with constant out-degree that admit a synchronizing road colouring. The subject of this paper is a pair of related conjectures that generalize the road colouring theorem to graphs with non-constant out-degree; we give reasons to believe that both of these conjectures are true. Our main results focus on two classes of graphs, proving both conjectures for one class of graphs and one of the conjectures for an additional class of graphs. We also present computer simulations that give some empirical evidence for the conjectures.
