The undecidability of joint embedding and joint homomorphism for hereditary graph classes
Samuel Braunfeld · Discrete Mathematics & Theoretical Computer Science · 2019
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. Comment: 17 pages; DMTCS version; initial version split