2022/07/25 by Russell J. Campbell, Campbell, Russell J., Nancy E. Clarke +3
Computer Science · Mathematics · #05C15 (Primary) #05C60 #05C85 #68R10 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2207.12526
openalex publication_date 2022/07/25 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
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.