Journal
COMBINATORICA
Volume 37, Issue 4, Pages 651-672Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s00493-015-3003-4
Keywords
-
Categories
Funding
- Hungarian OTKA [K-116769]
- Hungarian NSF (OTKA) [PD 104386]
- Hungarian Academy of Sciences
Ask authors/readers for more resources
Homomorphism duality pairs play a crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both sides are in finite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper we characterize the in finite-finite antichain dualities and in finite-finite dualities with trees or forests on the left hand side. This work builds on our earlier papers [6] that gave several examples of in finite-finite antichain duality pairs of directed graphs and [7] giving a complete characterization for caterpillar dualities.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available