Characterization of 4-critical triangle-free toroidal graphs (Q2668022)

A well-known theorem of Grötzsch states that every planar triangle-free graph is 3-colourable. However on other surfaces this is not true; \textit{J. Gimbel} and \textit{C. Thomassen} [Trans. Am. Math. Soc. 349, No. 11, 4555--4564 (1997; Zbl 0884.05039)] showed that triangle-free graphs on the projective plane are 3-colourable if and only if they do not have a bipartite quadrangulation as a subgraph. The paper under review considers the triangle-free graphs on the torus which are not 3-colourable. Since a graph is \(c\)-colourable if and only if does not contain a \((c+1)\)-critical subgraph, it is sufficient to describe the \((c+1)\)-critical subgraphs. The main result of the paper is an exact description of 4-critical triangle-free toroidal graphs. There are infinitely many of them, but they can all be obtained by triangulating faces of 186 template graphs. In a bit more detail, say a simple template \(T\) is a graph \(G_{T}\) 2-cell embedded in the torus together with a subset of its even-length faces. A graph drawn in the torus is represented by the simple template \(T\) if a graph homeomorphic to \(G\) is obtained by filling each face of \(T\) by an arbitrary triangulation. Then the detailed result is that there is a set \(\mathcal{T}\) of 186 simple templates with the properties that every 4-critical triangle-free graph drawn in the torus is represented by one of the simple templates in \(\mathcal{T}\) and no graph represented by a simple template in \(\mathcal{T}\) is 3-colourable. Recalling that the edge-width of a graph drawn in a surface is the length of its shortest non-contractible cycle, the result implies (for example) that every triangle-free graph drawn in the torus of edge-width at least six is 3-colourable. This has implications for algorithms to 3-colour triangle-free toroidal graphs where possible.