Question

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

Answer 1

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.''

---

Answer 2

With a different notion of undecidability, the following is another example. Ramsey's theorem says that if you 2-colour the edges of a countably infinite graph then there will be an infinite set of vertices such that all the edges between them have the same colour. A natural question one might then ask is whether if a graph with uncountably many vertices is 2-coloured you can find a subset of the vertices of the same size as the vertex set of the whole graph such that all edges inside the subset have the same colour. It turns out that you cannot necessarily do so unless the cardinality is enormous. Cardinalities that work are called weakly compact, and their existence is independent of ZFC. (This is the definition of "weakly compact" but there are many equivalent ways of defining them.)

Answer 3

My favorite undecidable problem in graph theory is the following: given a finite set of graphs $L$, is there a graph $G$ such that the neighborhood of each vertex in $G$ is isomorphic to a graph in $L$.

For a proof see: Peter M. Winkler. Existence of graphs with a given set of r-neighborhoods Journal of Combinatorial Theory, Series B, Volume 34, Issue 2, April 1983, Pages 165-176. (I am fairly sure this result is older, but that's the best I can do now.