8
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As far as I can see, Kalai discusses colorings of the dual graph of a triangulation, while I would like to color the triangulation itself. These two problems seem rather different. $\endgroup$ – Anton Kapustin Aug 13 '15 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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