The Complexity of the List Homomorphism Problem for Graphs
László Egri, Andrei Krokhin, Benoît Larose, Pascal Tesson · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2010
We completely classify the computational complexity of the list $\bH$-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph $\bH$ the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems.