Can anyone name a undecidable problem that is genuinely graph-related? (Genuine means: not a standard one in graph's disguise.)



Undecidable graph problems?
From a MathSciNet search:




---


Földes, Stéphane; Steinberg, Richard
A topological space for which graph embeddability is undecidable.
J. Combin. Theory Ser. B 29 (1980), no. 3, 342--344.


From the introduction: ``From Edmonds' permutation theorem and a generalization due to Stahl, it follows that graph embeddability is decidable for all surfaces, orientable as well as nonorientable. We show the existence of a topological space $\hat G$ such that there is no algorithm to decide whether a finite graph is embeddable in $\hat G$. In fact, $\hat G$ will be a path-connected subspace of the real plane.'' 




---


