The restrictive \(H\)-coloring problem (Q1764813)

Given two graphs \(G\) and \(H\) without multiple edges, an \(H\)-coloring of \(G\) is a homomorphism from \(G\) to \(H\) mapping the vertices in \(G\) to vertices in \(H\) in such a way that the image of an edge is also an edge. The \(H\)-coloring problem asks for the existence of an \(H\)-coloring while the counting \(H\)-coloring problem asks for the number of \(H\)-colorings of \(G\) (see the papers of \textit{P. Hell} and \textit{J. Nešetřil} [J. Comb. Theory, Ser. B 48, 92--110 (1990; Zbl 0639.05023)] and of \textit{M. Dyer} and \textit{C. Greenhill} [Random Struct. Algorithms 17, 260--289 (2000; Zbl 0965.68073)]). In this paper, restrictive variants of these problems are studied where the number of preimages of certain vertices is predetermined. The computational complexity of these problems is investigated. The authors show that their results apply also for the list versions and other extensions of the problems.