Characterization of 4-critical triangle-free toroidal graphs
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.
- Coloring graphs with fixed genus and girth
- Coloring near-quadrangulations of the cylinder and the torus
- Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\)
- Fine structure of 4-critical triangle-free graphs. III: General surfaces
- Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
- scientific article; zbMATH DE number 3482373 (Why is no real title available?)
- The chromatic number of a graph of girth 5 on a fixed surface
- Three-coloring Klein bottle graphs of girth five
- Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
- Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
- Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
This page was built for publication: Characterization of 4-critical triangle-free toroidal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2668022)
