Colorings of triangulations as a generalization of the four-color problem 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?
 A: 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.
A: 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.
A: These questions are covered in the excellent (as usual) post by Gil Kalai.
