论文标题
对小型锦标赛的注射式同构的复杂性和面向注射的色素的复杂性
Complexity of injective homomorphisms to small tournaments, and of injective oriented colourings
论文作者
论文摘要
考虑了针对定向图$ H $的定向图$ g $同构的局部注射率的几个可能的定义。在每种情况下，我们都会确定确定在给出$ g $时是否存在这种同态的复杂性，而$ h $是三个或更少的顶点的固定比赛。每个可能的定义都会导致面向局部的着色问题。在每种情况下都证明了二分法定理。
Several possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ are considered. In each case, we determine the complexity of deciding whether there exists such a homomorphism when $G$ is given and $H$ is a fixed tournament on three or fewer vertices. Each possible definition leads to a locally-injective oriented colouring problem. A dichotomy theorem is proved in each case.
