About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Combinatorial Theory. Series B
Paper
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.