Samuel Braunfeld - 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 - https://doi.org/10.23638/DMTCS-21-2-9
The undecidability of joint embedding and joint homomorphism for hereditary graph classes

Authors: Samuel Braunfeld

    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.

    https://doi.org/10.23638/DMTCS-21-2-9
    Source: arXiv.org:1903.11932
    Volume: Vol. 21 no. 2, Permutation Patters 2018
    Published on: December 13, 2019
    Accepted on: November 20, 2019
    Submitted on: March 29, 2019
    Keywords: Mathematics - Logic,Mathematics - Combinatorics
    Licence: Attribution 4.0 International (CC BY 4.0)

    Linked publications - datasets - softwares

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.1903.11932
    • 10.48550/arxiv.1903.11932
    The undecidability of joint embedding and joint homomorphism for hereditary graph classes
    Braunfeld, Samuel ;

    Share and export

    Consultation statistics

    This page has been seen 1246 times.
    This article's PDF has been downloaded 172 times.