The undecidability of joint embedding and joint homomorphism for hereditary graph classes

Abstract

We prove that the joint embedding property is undecidable for hereditary graph classes, via a reduction from the tiling problem. The proof is then adapted to show the undecidability of the joint homomorphism property as well.

17 pages; DMTCS version; initial version split

References in corpus (2)

• Pattern avoidance is not P-recursive
• Infinite Limits of Finite-Dimensional Permutation Structures, and their Automorphism Groups: Between Model Theory and Combinatorics

Cited by in corpus (3)

• Universal Horn Sentences and the Joint Embedding Property
• The undecidability of joint embedding for 3-dimensional permutation classes
• The Complexity of Combinations of Qualitative Constraint Satisfaction Problems