List homomorphism

List homomorphism --- предписанный гомоморфизм.

Given graphs [math]\displaystyle{ H }[/math], [math]\displaystyle{ G }[/math], and lists [math]\displaystyle{ L(v) \subseteq V(G) }[/math], [math]\displaystyle{ v \in V(H) }[/math], a list homo\-mor\-phism of [math]\displaystyle{ H }[/math] to [math]\displaystyle{ G }[/math], with respect to the lists [math]\displaystyle{ L }[/math], is a homomorphism [math]\displaystyle{ f: \; H \rightarrow G }[/math], such that [math]\displaystyle{ f(v) \in L(v) }[/math] for all [math]\displaystyle{ v \in V(H) }[/math]. For a fixed graph [math]\displaystyle{ G }[/math], the list homomorphism problem L-HOM [math]\displaystyle{ G }[/math] asks, whether or not an input graph [math]\displaystyle{ H }[/math] with lists [math]\displaystyle{ L }[/math] admits a list homomorphism of [math]\displaystyle{ H }[/math] to [math]\displaystyle{ G }[/math].