List Homomorphisms to Reflexive Graphs

Abstract

LetHbe a fixed graph. We introduce the following list homo morphism problem: Given an input graphGand for each vertexvofGa "list"L(v)⊆V(H), decide whether or not there is a homomorphismf:G→Hsuch thatf(v)∈L(v) for eachv∈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 whenHis an interval graph and prove that whenHis not an interval graph the problem isNP-complete. If the lists are restricted to induce connected subgraphs ofH, we give a polynomial time algorithm whenHis a chordal graph and prove that whenHis not chordal the problem is againNP-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 on irreflexive and general graphs. © 1998 Academic Press.