论文标题
道路问题和指示图的同态
The road problem and homomorphisms of directed graphs
论文作者
论文摘要
我们在道路（着色）问题的概括方面取得了进展。道路问题由Adler-Goodwyn-Weiss提出，并由Trahtman解决。 Ashley-Marcus-Tuncel提出了概括，并在某些特殊情况下解决了。我们解决了两个新的案件家族，其中一个概述了道路问题，并遵循Trahtman的解决方案，另一个案件概述了Ashley-Marcus-tuncel的结果，其证明与他们的证据完全不同。在此过程中，我们证明了某些图同构的纤维产物的普遍特性，这可能具有独立的兴趣。我们为相关结构和决策问题提供多项式时间算法。
We make progress on a generalization of the road (colouring) problem. The road problem was posed by Adler-Goodwyn-Weiss and solved by Trahtman. The generalization was posed, and solved in certain special cases, by Ashley-Marcus-Tuncel. We resolve two new families of cases, of which one generalizes the road problem and follows Trahtman's solution, and the other generalizes a result of Ashley-Marcus-Tuncel with a proof quite different from theirs. Along the way, we prove a universal property for the fiber product of certain graph homomorphisms, which may be of independent interest. We provide polynomial-time algorithms for relevant constructions and decision problems.
