Geodesic
The undecidability of joint embedding and joint homomorphism for hereditary graph classes
Discrete mathematics & theoretical computer science, Permutation Patters 2018, Tome 21 (2019) no. 2

Voir la notice de l'article provenant de la source Episciences

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. 
Braunfeld, Samuel. The undecidability of joint embedding and joint homomorphism for hereditary graph classes. Discrete mathematics & theoretical computer science, Permutation Patters 2018, Tome 21 (2019) no. 2. doi: 10.23638/DMTCS-21-2-9
@article{DMTCS_2019_21_2_a8,
     author = {Braunfeld, Samuel},
     title = {The undecidability of joint embedding and joint homomorphism for hereditary graph classes},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2019},
     volume = {21},
     number = {2},
     doi = {10.23638/DMTCS-21-2-9},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-2-9/}
}
TY  - JOUR
AU  - Braunfeld, Samuel
TI  - The undecidability of joint embedding and joint homomorphism for hereditary graph classes
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-2-9/
DO  - 10.23638/DMTCS-21-2-9
LA  - en
ID  - DMTCS_2019_21_2_a8
ER  - 
%0 Journal Article
%A Braunfeld, Samuel
%T The undecidability of joint embedding and joint homomorphism for hereditary graph classes
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-2-9/
%R 10.23638/DMTCS-21-2-9
%G en
%F DMTCS_2019_21_2_a8

Cité par Sources :