×

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)

MSC:

05C99 Graph theory
05C05 Trees
05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite