No label defined (Q4934398)

The graphs considered in this article may contain multiple edges but not loops. The edge-width of an embedding of a graph in an orientable surface is the length of the shortest noncontractable cycle. In [\textit{C. Thomassen}, Five-coloring graphs on the torus, J. Comb. Theory, Ser. B 62, No. 1, 11-33 (1994; Zbl 0805.05022)] it was shown that 6-regular graphs on the torus with edge-width at least 4 can be 5-coloured but that there are infinitely many 5-chromatic, 6-regular toroidal graphs with edge-width 3, and a characterization of the non-4-colourable, 6-regular graphs on torus was posed as an open problem. The article under review goes some way towards solving this problem. The main result is that a 6-regular toroidal graph embedded as an \(m\times n\) grid of any size shift with \(m\), \(n\geq 3\) and with edge-width at least 6 is 4-colourable. Other results treat the cases when some or all of these conditions are not satisfied, but a complete characterization remains an open problem. For the entire collection see [Zbl 0927.00021].