The complexity of frugal digraph homomorphisms

Stefan Bard, Gary MacGillivray, Jacobus Swarts

For an integer $t\ge 1$, a homomorphism of a digraph G to a digraph $H$ is $t$-frugal if no more than $t$ in-neighbours of any vertex of $G$ have the same image. There is a dicho…