List homomorphisms to reflexive graphs (Q1127870)

Let \(H\) be a fixed graph. In analogy to list colouring problems, we introduce the following list homomorphism problem: Given an input graph \(G\) and for each vertex \(v\) of \(G\) a `list' \(L(v) \subseteq V(H)\), decide whether or not there is a homomorphism (edge-preserving mapping of vertices) \(f : G \to H\) such that \(f(v) \in L(v)\) for each \(v \in V(G)\). We discuss this problem primarily in the context of reflexive graphs, i.e., graphs in which each vertex has a loop. We give a polynomial time algorithm to solve the problem when \(H\) is an interval graph and prove that when \(H\) is not an interval graph the problem is NP-complete. If the lists are restricted to induce connected subgraphs of \(H\), we give a polynomial time algorithm when \(H\) is a chordal graph and prove that when \(H\) is not chordal the problem is again NP-complete. We also argue that the complexity of certain other modifications of the problem (including the retract problem) are likely to be difficult to classify. Finally, we mention some newer results, joint with J. Huang, on irreflexive and general graphs.