Abstract
Given graphs G, H, and lists L(v) β V(H), v Ξ΅ V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) β V(H) such that __u__v Ξ΅ E(G) implies f(u)f(v) Ξ΅ E(H), and f(v) Ξ΅ L(v) for all v Ξ΅ V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) β V(H), v Ξ΅ V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NPβcomplete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NPβcomplete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called biβarc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a biβarc graph, and is NPβcomplete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. Β© 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61β80, 2003