LIST HOMOMORPHISMS TO REFLEXIVE GRAPHS

Let H be a fixed graph, We introduce the Following list homomorphism p roblem: Given an input graph G and for each vertex v of G a ''list'' L (v)subset of or equal to V(H), decide whether or not there is a homomo rphism f: G --> H such that f(v)epsilon L(v) for each v epsilon 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 tim e 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 t he lists are restricted to induce connected subgraphs of H, we give a polynomial time algorithm when H is a chordal graph and prove that whe n H is net chordal the problem is again NP-complete, We also argue tha t the complexity of certain other modifications of the problem (includ ing the retract problem) are likely to be difficult to classify. Final ly, we mention some newer results on irreflexive and general graphs. ( C) 1998 Academic Press.