## Chromatic Numbers of Simplicial Manifolds

Research output: Contribution to journal › Journal article › Research › peer-review

#### Standard

**Chromatic Numbers of Simplicial Manifolds.** / Lutz, Frank H.; Møller, Jesper M.

Research output: Contribution to journal › Journal article › Research › peer-review

#### Harvard

*Beitraege zur Algebra und Geometrie*, vol. 61, pp. 419–453. https://doi.org/10.1007/s13366-019-00474-7

#### APA

*Beitraege zur Algebra und Geometrie*,

*61*, 419–453. https://doi.org/10.1007/s13366-019-00474-7

#### Vancouver

#### Author

#### Bibtex

}

#### RIS

TY - JOUR

T1 - Chromatic Numbers of Simplicial Manifolds

AU - Lutz, Frank H.

AU - Møller, Jesper M.

PY - 2020

Y1 - 2020

N2 - 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 S3 with face vector f= (167 , 1579 , 2824 , 1412) and 2-chromatic number 5.

AB - 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 S3 with face vector f= (167 , 1579 , 2824 , 1412) and 2-chromatic number 5.

KW - Higher chromatic numbers

KW - Simplicial complex

KW - Steiner triple system

KW - Surface

KW - Triangulation

U2 - 10.1007/s13366-019-00474-7

DO - 10.1007/s13366-019-00474-7

M3 - Journal article

AN - SCOPUS:85075394387

VL - 61

SP - 419

EP - 453

JO - Beitraege zur Algebra und Geometrie

JF - Beitraege zur Algebra und Geometrie

SN - 0138-4821

ER -

ID: 233783171