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

Samuel Braunfeld

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

Samuel Braunfeld

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. Comment: 17 pages; DMTCS version; initial version split

Keywords

• Mathematics - Logic
• Mathematics - Combinatorics

Preview

Loading PDF preview...