Skip to main content
Source Link
Gil Kalai
  • 24.7k
  • 38
  • 235
  • 327

Let me mention here Thompson's three questions:

Question 1: Suppose that $G$ is the graph of a simple $d$-polytope with $n$ vertices. Suppose also that $n$ is even (this is automatic if $d$ is odd). Can we always properly color the edges of $G$ with $d$ colors?

Question 2 : Let $G$ be a dual graph of a triangulation of the $(d-1)$-dimensional sphere. Suppose that $G$ has an even number of vertices. Is $G$ $d$-edge colorable?

Question 3: Let $G$ be a dual graph of a triangulation of a $(d-1)$-dimensional manifold, $d \ge 4$. Suppose that $G$ has an even number of vertices. Is $G$ $d$-edge colorable?

Questions 1 and 2 coincides (by Steinitz's theorem) for $d=3$ and are equivalent there to the 4CT.

The starting point for these questions is a beautiful generalization for the 4CT proposed by Branko Grunbaum:

Grunbaum's conjecture: The dual graph of a triangulation of every two-dimensional manifold is alwayas 3-edge colorable.

Grunbaum's conjecture was disproved in 2009 by Martin Kochol.

Post Made Community Wiki by Gil Kalai