Let H be a fixed graph. We introduce the following list homomorphism problem: Given an input graph G and for each vertex v of G a ``list'' L(v) V(H), decide whether or not there is a homomorphism f :
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 on irreflexive and general graphs.
1998 Academic Press
1. Introduction
We consider finite undirected graphs which may have loops. A graph is reflexive if each vertex has a loop, and irreflexive if no vertex has a loop. A homomorphism f: G Γ H of a graph G to a graph H is a vertex mapping which preserves edges, i.e., a mapping f :
If there is a homomorphism of G to H we write G Γ H. Note that a homomorphism may in general identify adjacent vertices (onto a vertex which has a loop). Loops are usually ignored when properties of reflexive graphs are discussed. In particular, we say that a reflexive graph H is a tree, cycle, interval graph, or chordal graph, precisely when the graph obtained from H by removing all loops has the corresponding property (as defined, e.g., in [14]). As the only exception to this,