The complexity of List Homomorphism for graphs

We completely characterize the class of graphs for which the list homomorphism problem is in Logspace. Together with previous results, this implies that for every graph H, the list homomorphism problem is either NP-complete, NL-complete, L-complete or has finite duality. The central result is an inductive definition of graphs whose list homomorphism problem is solvable in Logspace. We obtain both algebraic and combinatorial characterizations. A characterization by forbidden (induced) subgraphs is given as well. In particular, the reflexive graphs whose list homomorphism problem is in Logspace are the trivially perfect graphs, or equivalently the graphs that contain no induced path of length three and no cycle of length four. In the irreflexive case, an analogous result is obtained: those with a list homomorphism problem in Logspace are the bipartite graphs that contain no induced path of length five and no cycle of length six. The general case can also be characterized by a set of forbidden subgraphs.