Chromatic Numbers of Simplicial Manifolds

Abstract

Higher chromatic numbers ${\chi }_s$ of simplicial complexes naturally generalize the chromatic number ${\chi }_1$ of a graph. In any fixed dimension $d$, the $s$-chromatic number ${\chi }_s$ of $d$-complexes can become arbitrarily large for $s\le \lceil d/2\rceil$ [6,18]. In contrast, ${\chi }_{d+1}=1$, and only little is known on ${\chi }_s$ for $\lceil d/2\rceil <s\le d$. A particular class of $d$-complexes are triangulations of $d$-manifolds. As a consequence of the Map Color Theorem for surfaces [29], the 2-chromatic number of any fixed surface is finite. However, by combining results from the literature, we will see that ${\chi }_2$ 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 ${\chi }_2$ 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 a 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 [18] along with embedding results [6] 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 [18], we obtain a rather small triangulation of the 3-dimensional sphere $S^3$ with face vector $f=(167,1579,2824,1412)$ and 2-chromatic number 5.

22 pages, 11 figures, revised presentation