5
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ genuinely graph-related = first arisen in graph theory $\endgroup$
    – Hans-Peter Stricker
    Jan 8, 2010 at 11:28
  • $\begingroup$ I don't know that the term "genuinely graph-related" is well-defined. $\endgroup$
    – Qiaochu Yuan
    Jan 8, 2010 at 16:46
  • $\begingroup$ Sorry, = was intended to mean "is intended to mean". $\endgroup$
    – Hans-Peter Stricker
    Jan 8, 2010 at 17:24
  • 5
    $\begingroup$ This is NOT a definition of "Sorry,", by the way. $\endgroup$
    – Hans-Peter Stricker
    Jan 8, 2010 at 17:26
  • $\begingroup$ Whether two graphs are quantum isomorphic... $\endgroup$
    – JP McCarthy
    Feb 10 at 17:48

3 Answers 3

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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?) $\endgroup$
    – Hans-Peter Stricker
    Jan 8, 2010 at 13:49
  • $\begingroup$ @HS: if you like an answer, please upvote it. You currently have 50% more questions than upvotes. $\endgroup$
    – Pete L. Clark
    Jan 8, 2010 at 14:05
  • $\begingroup$ Done! (But please note, that I accepted an answer to almost all of my questions. Isn't an upvote included in accepting an answer?) $\endgroup$
    – Hans-Peter Stricker
    Jan 8, 2010 at 14:22
  • $\begingroup$ 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. $\endgroup$
    – Pete L. Clark
    Jan 8, 2010 at 14:35
  • 1
    $\begingroup$ OK, I didn't know and will do better in the future! $\endgroup$
    – Hans-Peter Stricker
    Jan 8, 2010 at 14:47
7
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.