Braunfeld, Samuel - The undecidability of joint embedding and joint homomorphism for hereditary graph classes

dmtcs:5325 - Discrete Mathematics & Theoretical Computer Science, December 13, 2019, Vol. 21 no. 2, Permutation Patters 2018
The undecidability of joint embedding and joint homomorphism for hereditary graph classes

Authors: Braunfeld, Samuel

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.


Volume: Vol. 21 no. 2, Permutation Patters 2018
Published on: December 13, 2019
Submitted on: March 29, 2019
Keywords: Mathematics - Logic,Mathematics - Combinatorics


Share

Consultation statistics

This page has been seen 959 times.
This article's PDF has been downloaded 36 times.