Duality and Polynomial Testing of Tree Homomorphisms
Pavol Hell, Jaroslav Nešetřil, Xuding Zhu · Transactions of the American Mathematical Society · 1996
Let H H be a fixed digraph. We consider the H H -colouring problem, i.e., the problem of deciding which digraphs G G admit a homomorphism to H H . We are interested in a characterization in terms of the absence in G G of certain tree-like obstructions. Specifically, we say that H H has tree duality if, for all digraphs G G , G G is not homomorphic to H H if and only if there is an oriented tree which is homomorphic to G G but not to H H . We prove that if H H has tree duality then the H H -colouring problem is polynomial. We also generalize tree duality to bounded treewidth duality and prove a similar result. We relate these duality concepts to the notion of the X _ \underline X -property studied by Gutjahr, Welzl, and Woeginger. We then focus on the case when H H itself is an oriented tree. In fact, we are particularly interested in those trees that have exactly one vertex of degree three and all other vertices of degree one or two. Such trees are called triads. We have shown in a companion paper that there exist oriented triads H H for which the H H -colouring problem is N P NP -complete. We contrast these with several families of oriented triads