Chromatic Numbers of Simplicial Manifolds

Higher chromatic numbers χ_s of simplicial complexes naturally generalize the chromatic number χ₁ of a graph. In any fixed dimension d, the s-chromatic number χ_s of d-complexes can become arbitrarily large for s≤ ⌈ d/ 2 ⌉ (Bing in The geometric topology of 3-manifolds, Colloquium Publications, vol 40, American Mathematical Society, Providence, 1983; Heise et al. in Discrete Comput Geom 52:663–679, 2014). In contrast, χ_{d + 1}= 1 , and only little is known on χ_s for ⌈ d/ 2 ⌉ < s≤ d. A particular class of d-complexes are triangulations of d-manifolds. As a consequence of the Map Color Theorem for surfaces (Ringel in Map color theorem, Grundlehren der mathematischen Wissenschaften, vol 209, Springer, Berlin, 1974), the 2-chromatic number of any fixed surface is finite. However, by combining results from the literature, we will see that χ₂ for surfaces becomes arbitrarily large with growing genus. The proof for this is via Steiner triple systems and is non-constructive. In particular, up to now, no explicit triangulations of surfaces with high χ₂ were known. We show that orientable surfaces of genus at least 20 and non-orientable surfaces of genus at least 26 have a 2-chromatic number of at least 4. Via projective Steiner triple systems, we construct an explicit triangulation of a non-orientable surface of genus 2542 and with face vector f= (127 , 8001 , 5334) that has 2-chromatic number 5 or 6. We also give orientable examples with 2-chromatic numbers 5 and 6. For 3-dimensional manifolds, an iterated moment curve construction (Heise et al. 2014) along with embedding results (Bing 1983) can be used to produce triangulations with arbitrarily large 2-chromatic number, but of tremendous size. Via a topological version of the geometric construction of Heise et al. (2014), we obtain a rather small triangulation of the 3-dimensional sphere S³ with face vector f= (167 , 1579 , 2824 , 1412) and 2-chromatic number 5.