Colorings of triangulations as a generalization of the four-color problem

Question

My question can be viewed as a generalization of the four-color problem. Instead of a planar graph, consider a triangulation of a d-sphere. One wants to color vertices with N colors so that no two vertices connected by a 1-simplex have the same color. For a fixed d, is there an N which suffices for any triangulation? What are known upper bounds on such N?

Answer 1

When $d>2$, $N=\infty$. I got this fact from this preprint of Lutz and Möller which discusses "higher" coloring problems in manifolds.

There are at least two routes to this:

First, as mentioned as (3) after Definition 1.1, Walkup proved that $S^3$ (in fact, all closed, connected 3-manifolds) have neighborly triangulations, i.e. triangulations in which every pair of vertices is connected by an edge. See section 7 of Walkup's paper, which gives constructions of neighborly triangulations beginning with an arbitrary triangulation. Thus one can construct triangulations with arbitrarily large chromatic number.

For $S^d$ with $d>3$, one can take suspensions of triangulations of $S^{d-1}$.

Lutz and Möller give another proof in section 6 of their paper (see Lemma 6.2), which relies on a construction involving cyclic polytopes.

Answer 2

Already for $d=3$ the boundary complex of the cyclic polytope with n vertices has a complete graph and hence requires $n$ colors.

You may ask if restricting the class of triangulations can lead to interesting extension of the FCT. Some answers in Generalizations of the Four-Color theorem are relevant.

Answer 3

These questions are covered in the excellent (as usual) post by Gil Kalai.