Feder, Tomas; Hell, Pavol; Jing, Huang List homomorphisms and circular arc graphs. (English) Zbl 0985.05048 Combinatorica 19, No. 4, 487-505 (1999). The list homomorphism problem for a graph \(H\) has as input a graph \(G\) and lists \(L(v)\subseteq V(H)\) for the vertices \(v\in V(G)\). The output is a homomorphism \(f:G\to H\) with \(f(v)\in L(v)\) for every \(v\in V(G)\). It is shown that if \(H\) is loopless then this problem is polynomially solvable if \(\overline{H}\) is a circular arc graph of clique covering number 2, otherwise it is NP-complete. A new characterization is given for the former case. Reviewer: Péter Komjáth (Budapest) Cited in 2 ReviewsCited in 80 Documents MSC: 05C85 Graph algorithms (graph-theoretic aspects) 05C75 Structural characterization of families of graphs 05C15 Coloring of graphs and hypergraphs 68R10 Graph theory (including graph drawing) in computer science Keywords:graph homomorphisms; list chromatic number PDFBibTeX XMLCite \textit{T. Feder} et al., Combinatorica 19, No. 4, 487--505 (1999; Zbl 0985.05048) Full Text: DOI