## Abstract

Higher chromatic numbers χ_{s} of simplicial complexes naturally generalize the chromatic number χ_{1} 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 χ_{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 χ_{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 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^{3} with face vector f= (167 , 1579 , 2824 , 1412) and 2-chromatic number 5.

Original language | English |
---|---|

Journal | Beitraege zur Algebra und Geometrie |

Volume | 61 |

Pages (from-to) | 419–453 |

ISSN | 0138-4821 |

DOIs | |

Publication status | Published - 2020 |

## Keywords

- Higher chromatic numbers
- Simplicial complex
- Steiner triple system
- Surface
- Triangulation