Complexity of injective homomorphisms to small tournaments, and of injective oriented colourings
- Resource Type
- Working Paper
- Authors
- Campbell, Russell J.; Clarke, Nancy E.; MacGillivray, Gary
- Source
- Subject
- Mathematics - Combinatorics
05C15 (Primary), 05C60, 05C85, 68R10 (Secondary)
- Language
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.
Comment: 15 pages, 2 figures