Complexity of injective homomorphisms to small tournaments, and of injective oriented colourings

preprint2022arXivOpen access

Abstract

Several possible definitions of local injectivity for a homomorphism of an oriented graph GG to an oriented graph HH are considered. In each case, we determine the complexity of deciding whether there exists such a homomorphism when GG is given and HH 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.