Hell, Pavol Algorithmic aspects of graph homomorphisms. (English) Zbl 1035.05089 Wensley, C. D. (ed.), Surveys in combinatorics, 2003. Proceedings of the 19th British combinatorial conference, University of Wales, Bangor, UK, June 29–July 04, 2003. Cambridge: Cambridge University Press (ISBN 0-521-54012-7/pbk). Lond. Math. Soc. Lect. Note Ser. 307, 239-276 (2003). Author’s abstract: Homomorphisms are a useful model for a wide variety of combinatorial problems dealing with mappings and assignments, typified by scheduling and channel assignment problems. Homomorphism problems generalize graph colourings, and are in turn generalized by constraint satisfaction problems; they represent a robust intermediate class of problems – with greater modeling power than graph colourings, yet simpler and more manageable than general constraint satisfaction problems. We discuss various homomorphism problems from a computational perspective. One variant, with natural applications, gives each vertex a list of allowed images. Such list homomorphisms generalize list colourings, precolouring extensions, and graph retractions. Many algorithms for finding homomorphisms adapt well to finding list homomorphisms. Semi-homomorphisms are another variant; they generalize the kinds of partitions that homomorphisms induce, to allow both homomorphism type constraints, and constraints that correspond to homomorphisms of the complementary graphs. Surprisingly, semi-homomorphism partition problems cover a great variety of concepts arising in the study of perfect graphs. We illustrate some of the ideas leading to efficient algorithms for all these problems.For the entire collection see [Zbl 1020.00011]. Reviewer: Andreas Brandstädt (Rostock) Cited in 14 Documents MSC: 05C85 Graph algorithms (graph-theoretic aspects) 05C15 Coloring of graphs and hypergraphs 68R05 Combinatorics in computer science Keywords:graph homomorphism; graph coloring; constraint satisfaction PDFBibTeX XMLCite \textit{P. Hell}, Lond. Math. Soc. Lect. Note Ser. 307, 239--276 (2003; Zbl 1035.05089)