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?



Colorings of triangulations as a generalization of the four-color problem
When $d>2$, $N=\infty$. I got this fact from [this preprint of Lutz and Möller](http://arxiv.org/abs/1503.08251) 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](http://link.springer.com/article/10.1007%2FBF02392331?LI=true) 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](https://en.wikipedia.org/wiki/Cyclic_polytope).


