Colouring the 1-skeleton of $d$-dimensional triangulations

Abstract

While every plane triangulation is colourable with three or four colours, Heawood showed that a plane triangulation is 3-colourable if and only if every vertex has even degree. In $d\ge 3$ dimensions, however, every $k\ge d+1$ may occur as the chromatic number of some triangulation of ${\mathbb{S}}^d$. As a first step, Joswig structurally characterised which triangulations of ${\mathbb{S}}^d$ have a $(d+1)$-colourable 1-skeleton. In the 20 years since Joswig's result, no characterisations have been found for any $k>d+1$. In this paper, we structurally characterise which triangulations of ${\mathbb{S}}^d$ have a $(d+2)$-colourable 1-skeleton: they are precisely the triangulations that have a subdivision such that for every $(d-2)$-cell, the number of incident $(d-1)$-cells is divisible by three.

19 pages, 2 figures