# Undecidable graph problems?

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

-
genuinely graph-related = first arisen in graph theory – Hans Stricker Jan 8 '10 at 11:28
I don't know that the term "genuinely graph-related" is well-defined. – Qiaochu Yuan Jan 8 '10 at 16:46
Sorry, = was intended to mean "is intended to mean". – Hans Stricker Jan 8 '10 at 17:24
This is NOT a definition of "Sorry,", by the way. – Hans Stricker Jan 8 '10 at 17:26

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

-
Thanks! (How can such graph properties be characterized? Concerning the existence of another structure (graph, topological space or whatever) and a specific mapping/function: is there a standard name for such properties?) – Hans Stricker Jan 8 '10 at 13:49
@HS: if you like an answer, please upvote it. You currently have 50% more questions than upvotes. – Pete L. Clark Jan 8 '10 at 14:05
Done! (But please note, that I accepted an answer to almost all of my questions. Isn't an upvote included in accepting an answer?) – Hans Stricker Jan 8 '10 at 14:22
No, I don't believe it is. I have seen accepted answers with 0 upvotes. Anyway, you currently have 13 questions and 9 upvotes, which seems a little stingy. – Pete L. Clark Jan 8 '10 at 14:35
OK, I didn't know and will do better in the future! – Hans Stricker Jan 8 '10 at 14:47

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

-
@gowers: by "undecidability", do you mean that the answer may depend on which system of set theory is in force? – Emil Jan 8 '10 at 19:02
This reminds me of the "chromatic number of the plane" problem: en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem – Emil Jan 8 '10 at 19:03
Yes, I was using it as a synonym for "independent", as the sometimes is used that way. – gowers Jan 9 '10 at 9:12

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.

-