Hell, Pavol; Nešetřil, J.; Zhu, Xuding Duality of graph homomorphisms. (English) Zbl 0846.05093 Miklós, D. (ed.) et al., Combinatorics, Paul Erdős is eighty. Vol. 2. Budapest: János Bolyai Mathematical Society. Bolyai Soc. Math. Stud. 2, 271-282 (1996). After having surveyed results concerning homomorphism duality and complexity of the existence problem for graph homomorphisms the three authors succeed in proving a new result asserting that the problem of deciding whether or not the core (= digraph which is not homomorphic to any of its proper subgraphs) of a given digraph is an oriented tree, is NP-complete.For the entire collection see [Zbl 0837.00020]. Reviewer: R.Bodendiek (Kiel) Cited in 8 Documents MSC: 05C99 Graph theory 05C05 Trees 05C38 Paths and cycles 05C20 Directed graphs (digraphs), tournaments Keywords:homomorphism duality; complexity; graph homomorphisms; core; digraph; oriented tree; NP-complete PDFBibTeX XMLCite \textit{P. Hell} et al., Bolyai Soc. Math. Stud. 2, 271--282 (1996; Zbl 0846.05093)