Harry Metrebian
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, UK

Odd colouring on the torus]Odd colouring on the torus

A proper vertex-colouring of a simple graph $G$ is said to be odd if, for every non-isolated vertex $v$ of $G$, some colour appears an odd number of times in the neighbourhood of $v$. We show that if $G$ embeds in the torus, then it admits a proper odd vertex-colouring with at most $9$ colours.

§ INTRODUCTION

The concept of odd colouring was recently introduced by Petruševski and Škrekovski [6]. A proper odd vertex-colouring of a simple graph $G$, often referred to as an odd colouring for short, is a proper colouring $c$ of $V(G)$ with the property that, for every non-isolated vertex $v$ of $G$, there exists a colour $i$ such that $|c^{-1}(i) \cap N(v)|$ is odd: in other words, for every $v$, there is some colour that appears an odd number of times in the neighbourhood of $v$. The odd chromatic number of a graph $G$, denoted $\chi_o(G)$, is the smallest number $k$ such that $G$ admits an odd colouring using $k$ colours.

Petruševski and Škrekovski [6] used the discharging method to prove that every planar graph $G$ satisfies $\chi_o(G) \leq 9$, and conjectured that in fact $\chi_o(G) \leq 5$ for all planar graphs. Note that if true, this conjecture is the best possible, since $C_5$ requires $5$ colours. Petr and Portier [5] improved the upper bound to $\chi_o(G) \leq 8$, and Fabrici et al. [3] showed independently that in fact every planar graph has a conflict-free colouring with at most $8$ colours, meaning that there is a colouring such that for every $v$ some colour appears exactly once in its neighbourhood. Clearly any conflict-free colouring is an odd colouring.

A toroidal graph is a simple graph that can be embedded on the surface of a torus. We will demonstrate an upper bound on $\chi_o(G)$ for toroidal graphs:

Let $G$ be a toroidal graph. Then $\chi_o(G) \leq 9$.

Note that at least $7$ colours are sometimes required, since $K_7$ can be embedded in the torus.

Our proof mainly builds on the discharging techniques of Petruševski and Škrekovski [6]. Our application of the discharging method is rather more sensitive and leaves a special case that must be dealt with separately.

§ PROOF OUTLINE AND PRELIMINARIES

For convenience, we will refer to a proper odd colouring with at most $9$ colours as a nice colouring. From now on, we assume that there exists a toroidal graph which does not have a nice colouring, and $G = (V,E)$ will always denote a minimal such graph. Clearly $G$ is connected.

In our proof, we will often be faced with a situation where we have a colouring $c$ of $G\setminus\{v\}$, and we would like to find a colour that we can use at $v$ to extend $c$ to a nice colouring of $G$. There are two reasons why we might not be able to use a particular colour at $v$. Firstly, for each $w \in N(v)$, we cannot use $c(w)$ at $v$, since the resulting colouring would not be proper. We refer to such colours as forbidden at $v$ by properness. Secondly, for each $w \in N(v)$, there can be at most one colour $b(w)$ such that using $b(w)$ at $v$ would result in each colour being used an even number of times in $N(w)$. We refer to such colours as forbidden at $v$ by oddness. There are therefore at most $2d(v)$ colours forbidden at $v$ in total.

We will say that a colouring is proper at $v$ if $v$ is coloured differently from all its neighbours, and odd at $v$ to mean that some colour appears an odd number of times in $N(v)$. We will also use this terminology for partial colourings as long as they are defined at all the vertices of $N(v)$. Note that if $v$ has odd degree, then any colouring is automatically odd at $v$.

Note that the torus has Euler characteristic $0$, so for any toroidal graph we have a version of Euler's formula:
$$|V(G)| - |E(G)| + |F(G)| \geq 0.$$
Since $3|F(G)| \leq 2|E(G)|$, we have that $|E(G)| \leq 3|V(G)|$, and hence $\delta(G) \leq 6$. In order for equality to hold, $G$ must be $6$-regular and every face of $G$ must have 3 edges. In addition, equality must hold in Euler's formula, so every face of $G$ must be homeomorphic to a disk (see  [4], Chapter 3). In other words, $\delta(G) = 6$ iff $G$ is a $6$-regular triangulation of the torus.

In fact, for our minimal $G$, we must have $\delta(G) \geq 5$. This was proved by Petruševski and Škrekovski [6] in the context of planar graphs, but still holds for toroidal graphs. For completeness, we reproduce their proof here.

$G$ has minimum degree $\delta(G) \geq 5$.

Suppose that $G$ contains a vertex $v$ of degree $1$ or $3$. Let $c$ be a nice colouring of $G \setminus \{v\}$, which exists by minimality. We would like to extend $c$ to a nice colouring of $G$. There are now at most $3$ colours forbidden at $v$ by properness and at most $3$ forbidden by oddness, so there is some colour left over that can be used at $v$. Since $v$ has odd degree, the resulting colouring is odd at $v$ and therefore nice, which is a contradiction.

Now suppose instead that $G$ contains a vertex $v$ of degree $2$ or $4$. Let $w$ be an arbitrary neighbour of $v$, and let $G'$ be the graph constructed from $G$ by removing $v$ and then joining $w$ to every vertex in $N_G(v)$ to which it is not already adjacent. The graph $G'$ is toroidal, and so by minimality it has a nice colouring $c$. Now we return to $G$ and colour the vertices of $G\setminus\{v\}$ according to $c$. There are at most $8$ colours forbidden at $v$, leaving a colour that can be used at $v$. The colour $c(w)$ appears exactly once in $N(v)$ by construction, so the resulting colouring is odd at $v$. We therefore have a nice colouring of $G$, which is again a contradiction.

The rest of the proof will be structured as follows. We first use the discharging method and the minimality of $G$ to show that $G$ cannot contain a vertex of degree $5$. This leaves the case where $G$ is a $6$-regular triangulation. We then use the classification of $6$-regular triangulations of the torus by Altshuler [1] to show that every such triangulation admits a nice colouring, finishing the proof.

As is standard, we will refer to a vertex of degree $d$ as a $d$-vertex, and a vertex of degree at least $d$ as a $d^+$-vertex. The boundary of a face $f$ need not be connected, but it can be considered as a disjoint union of closed walks; we define the size of $f$, denoted $d(f)$, to be the total number of vertices appearing in this union of walks, counting with multiplicity. For example, a face whose boundary is a $k$-cycle has size $k$. We call a face of size $k$ a $k$-face, and a face of size at least $k$ a $k^+$-face.

§ DISCHARGING METHOD

In this section, we will deal with the case $\delta(G) = 5$. We will use the fact that the torus is locally homeomorphic to the plane, and therefore we will draw subgraphs of $G$ as if they were on the plane, although this may not always faithfully represent the embedding in the torus. However, the order of the edges around each vertex will be unambiguous and represented correctly.

Throughout the proof, there will be some occasions on which two vertices that are given different names could in fact be the same, or where two named vertices which are not defined to be adjacent could in fact be adjacent. However, this will never affect our arguments.

First, we will need a simple observation made by Petruševski and Škrekovski [6].

Suppose $v \in G$ is a $5$-vertex. Then $v$ has at most one neighbour of odd degree.

Suppose that $v$ has two neighbours $x$ and $y$ of odd degree. Let $c$ be a nice colouring of $G\setminus\{v\}$; we would like to extend $c$ to $v$. There are at most $5$ colours forbidden at $v$ by properness, and since $x$ and $y$ have odd degree, they cannot forbid colours at $v$ by oddness, so there are at most $3$ colours forbidden by oddness. This means there is a colour left over that can be used at $v$, and since $v$ has odd degree, the resulting colouring is nice, which is a contradiction.

We will now introduce our discharging rules. As is standard, we begin by assigning to every vertex $v \in G$ a charge $d(v)-6$ and to every face $f$ a charge $2d(f)-6$. By Euler's formula, the total charge over all vertices and faces of the graph is at most $0$.

The rules are as follows. If a vertex appears with multiplicity greater than $1$ in the closed walk around the boundary of a face, we consider each appearance to be a separate vertex when applying the rules.

* Every $5^+$-face sends charge $1.1$ to each incident $5$-vertex.

* Every $4$-face sends charge $1$ to each incident $5$-vertex, unless its incident vertices are, in order, two adjacent $5$-vertices and two adjacent $6^+$-vertices, in which case it sends charge $\f{3}{4}$ to each $5$-vertex.

* If $u$ and $v$ are $6^+$-vertices on a $4^+$-face $f$ that are adjacent along an edge of $f$ and also both incident to a $3$-face $uvw$, and $w$ is a $5$-vertex, then $f$ sends charge $\f{1}{2}$ to $w$.

* Suppose $v$ is a $7^+$-vertex with at least one neighbouring $5$-vertex. Let a block be a maximal set of $5$-vertices in $N(v)$ that appear consecutively in order around $v$. Now $v$ distributes its charge evenly between the blocks, and within each block the charge is distributed evenly between the vertices. For example, an $8$-vertex with $4$ neighbouring $5$-vertices in blocks of size $2$, $1$ and $1$ sends charge $\f{2}{3}$ to each vertex in a block of size $1$, and $\f{1}{3}$ to each of the vertices in the block of size $2$.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=1.49mm, fill=black
[enclosed, label=above: 5] (v1) at (0,1) ;
[enclosed] (v2) at (0.95,0.31) ;
[enclosed] (v3) at (0.59,-0.81) ;
[enclosed] (v4) at (-0.59,-0.81) ;
[enclosed] (v5) at (-0.95,0.31) ;

(v1) – (v2) – (v3) – (v4) – (v5) – (v1) ;
[->] (0,0) – (0,0.8) node[midway, right] (charge) 1.1;

at (0,-1.8) (R1);

[enclosed, label=above: 5] (w1) at (3.3,1) ;
[enclosed, label=right: $6^+$] (w2) at (4.3,0) ;
[enclosed, label=below: 5] (w3) at (3.3,-1) ;
[enclosed, label=left: $6^+$] (w4) at (2.3,0) ;

(w1) – (w2) – (w3) – (w4) – (w1) ;
[->] (3.3,0.1) – (3.3,0.8) node[midway, right] (charge2) 1;
[->] (3.3,-0.1) – (3.3,-0.8) node[midway, right] (charge3) 1;

[enclosed, label=above: 5] (x1) at (6.5,1) ;
[enclosed, label=right: 5] (x2) at (7.5,0) ;
[enclosed, label=below: $6^+$] (x3) at (6.5,-1) ;
[enclosed, label=left: $6^+$] (x4) at (5.5,0) ;

(x1) – (x2) – (x3) – (x4) – (x1) ;
[->] (6.5,0.1) – (6.5,0.8) node[midway, right] (charge2) $\f{3}{4}$;
[->] (6.6,0) – (7.3,0) node[midway, below] (charge3) $\f{3}{4}$;

at (4.9,-1.8) (R2);

[enclosed] (y1) at (-0.25,-3) ;
[enclosed] (y2) at (1.25,-3) ;
[enclosed, label=left: $6^+$] (y3) at (-0.25,-4.5) ;
[enclosed, label=right: $6^+$] (y4) at (1.25,-4.5) ;
[enclosed, label=below: 5] (y5) at (0.5,-5.8) ;
at (-0.05,-4.3) $u$;
at (1.05,-4.3) $v$;
at (0.75,-5.8) $w$;

(y1) – (y2) – (y4) – (y3) – (y1) ;
(y3) – (y5) – (y4) ;
[->] (0.5,-3.75) – (0.5,-5.6) ;
[right] at (0.5,-5) $\f{1}{2}$;

at (0.5,-6.8) (R3);

[enclosed] (u) at (5,-4.5) ;
[enclosed, label=above: 5] (z1) at (5,-3) ;
[right] at (5,-3.5) (l1) $\f{2}{3}$;
[enclosed, label=above right,xshift=-0.5mm,yshift=-0.5mm: $6^+$] (z2) at (6.06,-3.44) ;
[enclosed, label=right: 5] (z3) at (6.5,-4.5) ;
[below] at (6,-4.5) (l3) $\f{1}{3}$;
[enclosed, label=below right,xshift=-0.5mm,yshift=0.5mm: 5] (z4) at (6.06,-5.56) ;
[below left] at (5.71,-5.21) (l4) $\f{1}{3}$;
[enclosed, label=below: $6^+$] (z5) at (5,-6) ;
[enclosed, label=below left,xshift=0.5mm,yshift=0.5mm: $6^+$] (z6) at (3.94,-5.56) ;
[enclosed, label=left: 5] (z7) at (3.5,-4.5) ;
[below] at (4,-4.5) (l7) $\f{2}{3}$;
[enclosed, label=above left,xshift=0.5mm,yshift=-0.5mm: $6^+$] (z8) at (3.94,-3.44) ;

[decoration=markings, mark=at position 0.67 with >]
[postaction=decorate] (u) – (z1) ;
[postaction=decorate] (u) – (z3) ;
[postaction=decorate] (u) – (z4) ;
[postaction=decorate] (u) – (z7) ;

(u) – (z2) ;
(u) – (z5) ;
(u) – (z6) ;
(u) – (z8) ;

at (5,-6.8) (R4);

Examples of the discharging rules. The numbers next to vertices indicate their degrees, and the arrows indicate movement of charge.

After discharging, all faces and $6^+$-vertices have non-negative charge.

The only way in which a vertex can lose charge is by (R4), and by definition no vertex can end with negative charge after the application of this rule. Therefore a vertex can only end with negative charge if it began with negative charge, and by Claim <ref>, this is only the case for $5$-vertices.

We now turn to faces. When considering the total charge given out by a face $f$, we can imagine the charge $\f{1}{2}$ distributed by (R3) as being split into two $\f{1}{4}$ charges, one given to $u$ and one to $v$. Each $6^+$-vertex incident to $f$ is on at most two edges for which (R3) applies. Therefore $f$ gives out charge at most $\f{1}{2}$ for each incident $6^+$-vertex, and at most $1.1$ for each incident $5$-vertex.

If $f$ is a $7^+$-face, then the initial charge $2d(f)-6$ is greater than $1.1d(f)$, so trivially $f$ must finish with non-negative charge. If $f$ is a $6$-face, then it has initial charge $6$, but it cannot have more than four incident $5$-vertices: otherwise, one $5$-vertex would be adjacent to two others, contradicting Claim <ref>. Note that this is still true even if the boundary of $f$ consists of two disjoint $3$-cycles.  Therefore, by (R1) and (R3), $f$ gives out charge at most $4.4 + 1 < 6$, so it finishes with positive charge.

If $f$ is a $5$-face, then it has initial charge $4$, and by Claim <ref> it has at most three incident $5$-vertices. If it has exactly three, then the two remaining vertices are not adjacent on $f$ and therefore (R3) does not apply; thus $f$ gives out charge at most $3.3$. If instead $f$ has at most two incident $5$-vertices, then it gives out charge at most $2.2 + \f{3}{2} < 4$, so in either case $f$ finishes with positive charge.

If $f$ is a $4$-face, then it begins with charge $2$ and has at most two incident $5$-vertices by Claim <ref>. First suppose $f$ has exactly two $5$-vertices. If they are adjacent, then (R2) implies that they each receive charge $\f{3}{4}$. The remaining two vertices of $f$ are $6^+$-vertices, so the greatest additional charge that $f$ can give out is $\f{1}{2}$, by (R3). Thus $f$ gives out charge at most $2$, as required. If instead the two $5$-vertices are not adjacent, then they each receive charge $1$ by (R2), but (R3) does not apply and so $f$ again gives out total charge $2$.

Now consider the case where $f$ is a $4$-face with exactly one incident $5$-vertex. This vertex receives charge $1$, and (R3) applies to at most two edges of $f$, so it gives out total charge at most $2$. Finally, if every vertex of $f$ is a $6^+$-vertex, then it gives out charge at most $\f{1}{2}$ for each vertex, and so we are done.

Our graph $G$ begins with total charge at most $0$ and the rules preserve charge, so if $G$ has minimum degree $5$, Claim <ref> implies that some $5$-vertex must finish with charge at most $0$. If instead $\delta(G) = 6$, then as noted earlier, $G$ is a $6$-regular triangulation, and thus every vertex and face start and end with charge $0$. The discharging method therefore does not help when $\delta(G) = 6$, and we will have to treat this case separately.

For the remainder of this section, we will restrict ourselves to the case where $\delta(G) = 5$. Let $v$ be a $5$-vertex that has charge at most $0$ after the discharging process: in other words, $v$ receives total charge at most $1$ during discharging (recall that $v$ cannot give out charge). Let the neighbours of $v$ be $v_1$, $v_2$, $v_3$, $v_4$ and $v_5$ in anticlockwise order.

The five faces around $v$ are all different.

Suppose that two of the faces around $v$ are the same face $f$. This face clearly must be a $4^+$-face. By the discharging rules, $f$ sends charge at least $\f{3}{4}$ to $v$ for each appearance of $v$ on the boundary of $f$, so $f$ sends total charge at least $\f{3}{2}$ to $v$, a contradiction.

We will make use the following lemma to eliminate the cases in the remainder of the proof.

Suppose that the edges $v_1v_2$, $v_2v_3$ and $v_3v_4$ are all present in $G$, and that $v_2$ and $v_3$ are $6$-vertices with a common neighbour $x \neq v$. Let $c$ be a nice colouring of $G \setminus \{v\}$ in which $c(v_1)$, $c(v_2)$, $c(v_3)$ and $c(v_4)$ are all distinct. Then $v_2$ and $v_3$ do not forbid two distinct colours at $v$ by oddness unless at least one is already forbidden by properness.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=.15cm, fill=black
[enclosed, label=above,xshift=2mm: $v$] (v) at (0,0) ;
[enclosed, label=above: $v_5$] (v5) at (0,1) ;
[enclosed, label=right,yshift=1mm: $v_4$] (v4) at (0.95,0.31) ;
[enclosed, label=right,yshift=2mm: $v_3$] (v3) at (0.59,-0.81) ;
[enclosed, label=left,yshift=2mm: $v_2$] (v2) at (-0.59,-0.81) ;
[enclosed, label=left,yshift=1mm: $v_1$] (v1) at (-0.95,0.31) ;
[enclosed, label=below: $x$] (x) at (0,-1.6) ;

(v) – (v1) ;
(v) – (v2) ;
(v) – (v3) ;
(v) – (v4) ;
(v) – (v5) ;
(v1) – (v2) – (v3) – (v4) ;
(v2) – (x) – (v3) ;
(v2) – ++(180:5mm) ;
(v2) – ++(240:5mm) ;
(v3) – ++(0:5mm) ;
(v3) – ++(300:5mm) ;

The setting of Lemma <ref>. All edges from $v$, $v_2$ and $v_3$ are shown.

Suppose that a colouring $c$ exists as above, and let $c(v_i) = i$ for $i = 1,2,3,4$. Suppose further that $v_2$ and $v_3$ forbid colours $2'$ and $3'$ respectively at $v$ by oddness, where $2' \neq 3'$ and $2',3' \notin \{1,2,3,4\}$. Now the colours of the neighbours of $v_2$ in $G \setminus \{v\}$ must be $1,1,3,3,2'$ in some order. In particular, $c(x) \in \{1,3,2'\}$. Similarly, consideration of the colours around $v_3$ shows that $c(x) \in \{2,4,3'\}$. But now there is no possible colour for $x$ and we have a contradiction.

We will need one more structural lemma.

$G$ does not contain two adjacent $5$-vertices which have two common neighbours.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=.15cm, fill=black
[enclosed, label=left: $u$] (u) at (-0.5,0) ;
[enclosed, label=right: $v$] (v) at (0.5,0) ;
[enclosed, label=above: $x$] (x) at (0,0.86) ;
[enclosed, label=below: $y$] (y) at (0,-0.86) ;
[enclosed, label=above left,xshift=0.5mm,yshift=-0.5mm: $w_1$] (w1) at (-1.21,0.71) ;
[enclosed, label=below left,xshift=0.5mm,yshift=0.5mm: $w_2$] (w2) at (-1.21,-0.71) ;
[enclosed, label=above right,xshift=-0.5mm,yshift=-0.5mm: $z_1$] (z1) at (1.21,0.71) ;
[enclosed, label=below right,xshift=-0.5mm,yshift=0.5mm: $z_2$] (z2) at (1.21,-0.71) ;

(u) – (v) ;
(w1) – (u) – (x) – (v) – (z1) ;
(w2) – (u) – (y) – (v) – (z2) ;

The setting of Lemma <ref>. All edges from $u$ and $v$ are shown.

Suppose to the contrary that $u$ and $v$ are adjacent $5$-vertices with common neighbours $x$ and $y$. Let the two remaining neighbours of $u$ be $w_1$ and $w_2$, and let the two remaining neighbours of $v$ be $z_1$ and $z_2$. Note that we could have some $w_i = z_j$.

Consider the graph $G' = G/\{u, v\}$ formed by contracting the edge $uv$ to form a single vertex $\{u, v\}$. By the minimality of $G$, this graph has a nice colouring, which we will call $c$. We will use $c$ to colour the vertices of $G \setminus \{u,v\}$, and show that we can always choose colours at $u$ and $v$ to produce an odd colouring of $G$. Note that any colouring of $G$ will be odd at $u$ and $v$, since they both have odd degree.

Suppose that we colour $u$ with $c(\{u,v\})$. The resulting partial colouring is both proper and odd at each $w_i$ that is not the same as some $z_j$, since $c$ is an odd colouring of $G'$. Note that $u$ has degree $5$ so cannot forbid a colour at $v$ by oddness. For every remaining neighbour $t$ of $v$, let $b(t)$ be the colour that $t$ forbids at $v$ by oddness, if it exists. There are at most $5$ colours forbidden at $v$ by properness, and at most $4$ forbidden by oddness. Therefore there is always a colour available at $v$ to produce an odd colouring of $G$ unless the $9$ colours $c(\{u,v\}), c(x), c(y), c(z_1), c(z_2), b(x), b(y), b(z_1), b(z_2)$ are all distinct. Similarly, we could colour $v$ with $c(\{u,v\})$ instead of $u$, and define $b$ as above; there is no ambiguity in the definitions of $b(x)$ and $b(y)$ since the neighbourhoods of $x$ and $y$ have the same multisets of colours in each case. This partial colouring extends to an odd colouring of $G$ unless $c(\{u,v\}), c(x), c(y), c(w_1), c(w_2), b(x), b(y), b(w_1), b(w_2)$ are all distinct.

Suppose that the two sets of $9$ colours above are indeed distinct. Now we assign the colour $b(x)$ to $u$ and $b(y)$ to $v$. This results in a proper colouring of $G$ by distinctness. This colouring is odd at $w_i$ and $z_j$, also by distinctness. Finally, $c(\{u,v\})$ and $b(y)$ each appear an odd number of times in $N(x)$, since they are distinct from each other and from $b(x)$; similarly $c(\{u,v\})$ and $b(x)$ appear an odd number of times in $N(y)$. Thus $G$ has a nice colouring, which is a contradiction.

The five faces around $v$ are all $3$-faces.

First note that, by (R1), a $5$-face would send charge greater than $1$ to $v$, which is impossible. As noted previously, a $4$-face sends charge at least $\f{3}{4}$, so $v$ can be incident to at most one $4$-face. Let the $4$-face be $v_5vv_1w$. Now Lemma <ref> implies that $v_2$, $v_3$ and $v_4$ are all $6^+$-vertices.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=.15cm, fill=black
[enclosed, label=above,xshift=2mm: $v$] (v) at (0,0) ;
[enclosed, label=above: $v_5$] (v5) at (0,1) ;
[enclosed, label=right: $v_4$] (v4) at (0.95,0.31) ;
[enclosed, label=below right,xshift=-0.5mm,yshift=0.3mm: $v_3$] (v3) at (0.59,-0.81) ;
[enclosed, label=below left,xshift=0.5mm,yshift=0.3mm: $v_2$] (v2) at (-0.59,-0.81) ;
[enclosed, label=left: $v_1$] (v1) at (-0.95,0.31) ;
[enclosed, label=above left,xshift=0.5mm,yshift=-0.5mm: $w$] (w) at (-0.75,1) ;

(v) – (v1) ;
(v) – (v2) ;
(v) – (v3) ;
(v) – (v4) ;
(v) – (v5) ;
(v1) – (v2) – (v3) – (v4) – (v5) – (w) – (v1) ;

$v$ and its surrounding faces

Let $c$ be a nice colouring of $G\setminus \{v\}$, which must exist by the minimality of $G$. We now divide into $3$ cases.

* $v$ has a neighbouring $5$-vertex.

* All the neighbours of $v$ are $6^+$-vertices, and $|c(N(v))| = 4$.

* All the neighbours of $v$ are $6^+$-vertices, and $|c(N(v))| = 5$.

Note that we must have $|c(N(v))| \geq 4$, otherwise there would be at most $8$ colours forbidden at $v$ and we could extend $c$ to a nice colouring of $G$. Henceforth, if the edge $v_iv_{i+1}$ is present, we will refer to the face adjacent to $vv_iv_{i+1}$ along $v_iv_{i+1}$ as the external face along $v_iv_{i+1}$.

Case 1: $v$ has a neighbouring $5$-vertex.

Without loss of generality, the $5$-vertex is $v_1$, and so $v_5$ is a $6^+$-vertex. Now $v_1$ does not forbid a colour at $v$ by oddness, so we must have $|c(N(v))| = 5$, otherwise there would be at most $8$ colours forbidden at $v$.

Note that a vertex of degree $d \geq 7$ can have at most $\left\lfloor\f{d}{2}\right\rfloor$ neighbouring blocks in the terminology of (R4). Since the total charge given out is $d-6$, this implies that a $7$-vertex gives out charge at least $\f{1}{3}$ to every block, and an $8^+$-vertex gives out charge at least $\f{1}{2}$.

If either $v_3$ or $v_4$ is a $7^+$-vertex, then by (R4) it sends charge at least $\f{1}{3}$ to $v$, since $v$ is a singleton block. This is a contradiction because $v$ already receives charge at least $\f{3}{4}$ from the $4$-face. Hence $v_3$ and $v_4$ are both $6$-vertices.

By (R3), the external face along $v_3v_4$ cannot be a $4^+$-face, otherwise it would send charge $\f{1}{2}$ to $v$. Hence it is a $3$-face, and so $v_3$ and $v_4$ have a common neighbour that is not $v$. Now we can apply Lemma <ref> to $v_2$, $v_3$, $v_4$, $v_5$, which implies that $v_3$ and $v_4$ cannot forbid distinct colours at $v$ by oddness that are not already in $c(N(v))$. Hence at most $8$ colours are forbidden at $v$ and we can extend $c$ to $v$. This completes Case 1.

Case 2: All the neighbours of $v$ are $6^+$-vertices, and $|c(N(v))| = 4$.

The external faces along $v_1v_2$, $v_2v_3$, $v_3v_4$ and $v_4v_5$ must all be $3$-faces, otherwise they would give charge $\f{1}{2}$ to $v$ by (R3). Denote the common neighbour of $v_2$ and $v_3$ on this external $3$-face by $x$, and the corresponding common neighbour of $v_3$ and $v_4$ by $y$.

As in Case 1, if any of $v_2$, $v_3$, $v_4$ is a $7^+$-vertex then it sends charge at least $\f{1}{3}$ to $v$ by (R4). Hence $v_2$, $v_3$, $v_4$ are all $6$-vertices. Lemma <ref> now applies to either $\{v_1, v_2, v_3, v_4\}$ or $\{v_2, v_3, v_4, v_5\}$, giving a contradiction, unless $c(v_2) = c(v_4)$. Let $c(v_i) = i$ for $i = 1,2,3,5$.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=.15cm, fill=black
[enclosed, label=above,xshift=2mm: $v$] (v) at (0,0) ;
[enclosed, label=above: $v_5$] (v5) at (0,1) ;
[enclosed, label=right,yshift=-1mm: $v_4$] (v4) at (0.95,0.31) ;
[enclosed, label=right,yshift=-1mm: $v_3$] (v3) at (0.59,-0.81) ;
[enclosed, label=left,yshift=-1mm: $v_2$] (v2) at (-0.59,-0.81) ;
[enclosed, label=left,yshift=1mm: $v_1$] (v1) at (-0.95,0.31) ;
[enclosed, label=above left,xshift=0.5mm,yshift=-0.5mm: $w$] (w) at (-0.75,1) ;
[enclosed] (x1) at (-1.55,-0.48) ;
[enclosed, label=below: $x$] (x) at (0,-1.6) ;
[enclosed, label=right,yshift=-1mm: $y$] (y) at (1.55,-0.48) ;
[enclosed] (x4) at (0.95,1.29) ;

(v) – (v1) ;
(v) – (v2) ;
(v) – (v3) ;
(v) – (v4) ;
(v) – (v5) ;
(v1) – (v2) – (v3) – (v4) – (v5) – (w) – (v1) ;
(v1) – (x1) – (v2) – (x) – (v3) – (y) – (v4) – (x4) – (v5) ;
(v2) – ++(234:5mm) ;
(v3) – ++(306:5mm) ;
(v4) – ++(18:5mm) ;

The setting of Case 2. All edges from $v$, $v_2$, $v_3$ and $v_4$ are shown.

Consider the colours in $N(v_2)\setminus\{v\}$. $v_2$ must forbid a colour $2' \notin \{1,2,3,5\}$ at $v$ by oddness, so the vertices of $N(v_2)\setminus\{v\}$ must have colours $1,1,3,3,2'$ in some order. Hence $c(x) \in \{1,2'\}$. Similarly $c(y) \in \{5,4'\}$, where $4'$ is defined analogously to $2'$.

But now $N(v_3)\setminus\{v\}$ has two vertices of colour $3$ as well as one of colour $1$ or $2'$ and one of colour $5$ or $4'$. There is therefore no way for $v_3$ to forbid a new colour $3'$ at $v$ by oddness, and so there are at most $8$ colours forbidden at $v$. This completes Case 2.

Case 3: All the neighbours of $v$ are $6^+$-vertices, and $|c(N(v))| = 5$.

First, note that the external faces along $v_1v_2$, $v_2v_3$, $v_3v_4$ and $v_4v_5$ must all be $3$-faces, as in Case 2. For $i = 1,2,3,4$, let $x_i$ be the common neighbour of $v_i$ and $v_{i+1}$ on this external $3$-face, and recall that $w$ is the final vertex of the $4$-face containing $v_1$, $v$ and $v_5$. Let $c(v_i) = i$, and let the colour that $v_i$ forbids at $v$ by oddness be $i'$, if it exists.

We also have that $v_2$, $v_3$ and $v_4$ must all be $6$-vertices, since if any were $7^+$-vertices, they would give charge at least $\f{1}{3}$ to $v$ by (R4). In addition, if either $v_1$ or $v_5$ is a $7^+$-vertex, then it also gives charge at least $\f{1}{3}$ to $v$ except in the event that $\{v\}$ is not a block; this only happens if $w$ is a $5$-vertex. However, in this case the face $vv_1wv_5$ gives charge $1$ to $v$ by (R2), and the $7^+$-vertex still sends some positive charge to $v$, which is a contradiction. Hence all the neighbours of $v$ are $6$-vertices.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=.15cm, fill=black
[enclosed, label=above,xshift=2mm: $v$] (v) at (0,0) ;
[enclosed, label=above left: $v_5$] (v5) at (0,1) ;
[enclosed, label=right,yshift=-1mm: $v_4$] (v4) at (0.95,0.31) ;
[enclosed, label=right,yshift=-1mm: $v_3$] (v3) at (0.59,-0.81) ;
[enclosed, label=left,yshift=-1mm: $v_2$] (v2) at (-0.59,-0.81) ;
[enclosed, label=left,yshift=-1mm: $v_1$] (v1) at (-0.95,0.31) ;
[enclosed, label=above left,xshift=0.5mm,yshift=-0.5mm: $w$] (w) at (-0.75,1) ;
[enclosed, label=left,yshift=-1mm: $x_1$] (x1) at (-1.55,-0.48) ;
[enclosed, label=below: $x_2$] (x2) at (0,-1.6) ;
[enclosed, label=right,yshift=-1mm: $x_3$] (x3) at (1.55,-0.48) ;
[enclosed, label=right,yshift=2mm: $x_4$] (x4) at (0.95,1.29) ;

(v) – (v1) ;
(v) – (v2) ;
(v) – (v3) ;
(v) – (v4) ;
(v) – (v5) ;
(v1) – (v2) – (v3) – (v4) – (v5) – (w) – (v1) ;
(v1) – (x1) – (v2) – (x) – (v3) – (y) – (v4) – (x4) – (v5) ;
(v1) – ++(162:5mm) ;
(v2) – ++(234:5mm) ;
(v3) – ++(306:5mm) ;
(v4) – ++(18:5mm) ;
(v5) – ++(90:5mm) ;

The setting of Case 3. All edges from $v$ and each $v_i$ are shown.

Lemma <ref> applies to both $\{v_1, v_2, v_3, v_4\}$ and $\{v_2, v_3, v_4, v_5\}$, and there must be at least $4$ colours forbidden by oddness at $v$. Thus the only possibility is that these are $1',2',4',5'$, while $v_3$ does not forbid a colour by oddness at $v$ that is not already forbidden in some other way.

The colours of the vertices of $N(v_2)\setminus\{v\}$ must be $1,1,3,3,2'$, and so $c(x_2) \in \{1,2'\}$. Similarly $c(x_3) \in \{5,4'\}$. Let $c'$ be the restriction of $c$ to $G\setminus\{v,v_2\}$. We will extend $c'$ to a nice colouring of $G$.

First, assign colour $2$ to $v$. This produces a proper partial colouring that is odd at $v_4$ and $v_5$. The colouring is also odd at $v_2$, since $v_2$ has exactly one neighbour of colour $2$. In addition, the colours $2,4,c(x_2),c(x_3)$ are all distinct and all already used in $N(v_3)$, so $v_3$ cannot forbid a colour at $v_2$ by oddness. Therefore there are at most $8$ colours forbidden at $v_2$: the $4$ colours of its neighbours, and at most $4$ colours forbidden by oddness, since neither $v$ nor $v_3$ forbids a colour by oddness. Hence there is a colour left over that we can use to colour $v_2$. This finishes the proof of Proposition <ref>.

We now know that all the faces around $v$ are $3$-faces. Lemma <ref> therefore implies that all the $v_i$ are $6^+$-vertices. As before, let $c$ be a nice colouring of $G\setminus\{v\}$. Once again, we must have $|c(N(v))| \geq 4$, so we first rule out the case $|c(N(v))| = 4$.

We have $|c(N(v))| = 5$.

Suppose that $|c(N(v))| = 4$. Without loss of generality, we have $c(v_i) = i$ for $i = 1,2,3,5$ and $c(v_4) = 2$. Since all $9$ colours must be forbidden at $v$ by either properness or oddness, every $v_i$ forbids a colour by oddness, which we call $i'$ as before. Thus every $v_i$ has even degree.

By Lemma <ref>, if $v_1$ and $v_2$ are both $6$-vertices and the external face along $v_1v_2$ is a $3$-face, then one of $v_1$ and $v_2$ does not forbid a distinct colour by oddness, which is a contradiction. Hence either the external face along $v_1v_2$ is a $4^+$-face, giving charge $\f{1}{2}$ to $v$ by (R3), or one of $v_1$ and $v_2$ is an $8^+$-vertex, giving charge at least $\f{1}{2}$ to $v$ by (R4). Similarly, either the external face along $v_4v_5$ is a $4^+$-face or one of $v_4$ and $v_5$ is an $8^+$-vertex. Together these give a total charge of at least $1$ to $v$. This implies that $v$ cannot receive any further charge: in particular, the external faces along $v_2v_3$ and $v_3v_4$ are $3$-faces, and $v_3$ has degree $6$. Let $x$ be the common neighbour of $v_2$ and $v_3$ on this external face, and let $y$ be the corresponding common neighbour of $v_3$ and $v_4$.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=.15cm, fill=black
[enclosed, label=above,xshift=2mm: $v$] (v) at (0,0) ;
[enclosed, label=above: $v_5$] (v5) at (0,1) ;
[enclosed, label=right,yshift=1mm: $v_4$] (v4) at (0.95,0.31) ;
[enclosed, label=right,yshift=-1mm: $v_3$] (v3) at (0.59,-0.81) ;
[enclosed, label=left,yshift=-1mm: $v_2$] (v2) at (-0.59,-0.81) ;
[enclosed, label=left,yshift=1mm: $v_1$] (v1) at (-0.95,0.31) ;
[enclosed, label=below: $x$] (x) at (0,-1.6) ;
[enclosed, label=right,yshift=-1mm: $y$] (y) at (1.55,-0.48) ;

(v) – (v1) ;
(v) – (v2) ;
(v) – (v3) ;
(v) – (v4) ;
(v) – (v5) ;
(v1) – (v2) – (v3) – (v4) – (v5) – (v1) ;
(v2) – (x) – (v3) – (y) – (v4) ;
(v3) – ++(306:5mm) ;

The case $|c(N(v))| = 4$. All edges from $v$ and $v_3$ are shown.

Suppose first that $v_2$ and $v_4$ are both $6$-vertices. Then the colours in $N(v_2)\setminus\{v\}$ are $1,1,3,3,2'$ in some order, so $c(x) \in \{1,2'\}$. Similarly $c(y) \in \{5,4'\}$. But now $v_3$ cannot forbid a new colour $3'$ by oddness. So at least one of $v_2$ and $v_4$ must be an $8^+$-vertex. Without loss of generality it is $v_2$.

Note that $v_2$ must send charge exactly $\f{1}{2}$ to $v$, since otherwise $v$ would receive total charge greater than $1$. The only way this can happen is if $v_2$ has degree exactly $8$ and the neighbours of $v_2$ are alternately $5$-vertices and $6^+$-vertices. This implies that $x$ is a $5$-vertex.

Now consider the restriction $c'$ of $c$ to $G\setminus\{v,v_3\}$. We will extend this to a nice colouring of $G$. First we assign the colour $3$ to $v$. This produces a proper partial colouring that is odd at $v_1$ and $v_5$; it is also odd at $v_3$, since $v_3$ has exactly one neighbour of colour $3$. Since $v_3$ forbids a colour by oddness at $v$ in the colouring $c$, we must have $|c(N(v_3)\setminus\{v\})| \leq 3$, and hence after colouring $v$ we have used at most $4$ colours in $N(v_3)$. In addition, $v$ and $x$ both have odd degree, so there at most $4$ colours forbidden by oddness at $v_3$. There is therefore a colour left over to use at $v_3$, and we are done.

We are now ready to finish the proof for the case $\delta(G) = 5$. Let $c$ be a nice colouring of $G\setminus\{v\}$. Since we know $|c(N(v))| = 5$, the $v_i$ must together forbid the remaining $4$ colours by oddness. Therefore, without loss of generality, we have that for $i = 1,2,4,5$, $v_i$ forbids a colour $i' \notin \{1,2,3,4,5\}$, where all the $i'$ are distinct. This implies that all the $v_i$ except possibly $v_3$ have even degree.

If the external face along $v_5v_1$ is a $3$-face and $v_1$ and $v_5$ are both $6$-vertices, then Lemma <ref> applied to $\{v_4, v_5, v_1, v_2\}$ gives a contradiction, since $1'$ and $5'$ are distinct from each other and all the other colours. Therefore either the external face along $v_5v_1$ is a $4^+$-face, or one of $v_1$ and $v_5$ is an $8^+$-vertex. In either case, charge at least $\f{1}{2}$ is sent to $v$.

We can similarly apply Lemma <ref> to $\{v_3, v_4, v_5, v_1\}$ and $\{v_5, v_1, v_2, v_3\}$. This shows that either the external face along $v_4v_5$ is a $4^+$-face or one of $v_4$ and $v_5$ is an $8^+$-vertex, and that either the external face along $v_1v_2$ is a $4^+$-face or one of $v_1$ and $v_2$ is an $8^+$-vertex.

In particular, if both $v_1$ and $v_5$ are $6$-vertices, then this implies that each of the edges $v_1v_2$ and $v_4v_5$ must either have an external $4^+$-face or contain an $8^+$-vertex. Together, these send charge at least $1$ to $v$, implying that the external face along $v_1v_5$ cannot be a $4^+$-face. But this is a contradiction, since we have just shown that if $v_1$ and $v_5$ are both $6$-vertices then the external face along $v_5v_1$ is a $4^+$-face. Hence at least one of $v_1$ and $v_5$ is an $8^+$-vertex.

Suppose without loss of generality that $v_1$ is an $8^+$-vertex. We still require that either the external face along $v_4v_5$ is a $4^+$-face or one of $v_4$ and $v_5$ is an $8^+$-vertex. In either case, $v$ receives total charge at least $1$. As in the proof of Proposition <ref>, in order for the total charge to be exactly $1$, we must have that $v_1$ has degree exactly $8$, $v_2$ is a $6$-vertex, and the external face along $v_1v_2$ is a $3$-face. Let $x$ be the common neighbour of $v_1$ and $v_2$ on this face. Again, as in the proof of Proposition <ref>, the neighbours of $v_1$ must alternate between $5$-vertices and $6^+$-vertices, so $x$ has degree $5$.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=.15cm, fill=black
[enclosed, label=above,xshift=2mm: $v$] (v) at (0,0) ;
[enclosed, label=above: $v_5$] (v5) at (0,1) ;
[enclosed, label=right,yshift=1mm: $v_4$] (v4) at (0.95,0.31) ;
[enclosed, label=right,yshift=-2mm: $v_3$] (v3) at (0.59,-0.81) ;
[enclosed, label=left,yshift=-1mm: $v_2$] (v2) at (-0.59,-0.81) ;
[enclosed, label=left,yshift=-1mm: $v_1$] (v1) at (-0.95,0.31) ;
[enclosed, label=left,yshift=-1mm: $x$] (x) at (-1.55,-0.48) ;

(v) – (v1) ;
(v) – (v2) ;
(v) – (v3) ;
(v) – (v4) ;
(v) – (v5) ;
(v1) – (v2) – (v3) – (v4) – (v5) – (v1) ;
(v1) – (x) – (v2) ;
(v2) – ++(240:5mm) ;
(v2) – ++(300:5mm) ;
(v1) – ++(66:5mm) ;
(v1) – ++(96:5mm) ;
(v1) – ++(126:5mm) ;
(v1) – ++(156:5mm) ;

The case $|c(N(v))| = 5$, where $v_1$ is an $8$-vertex without loss of generality. All edges from $v$, $v_1$ and $v_2$ are shown.

Now we restrict $c$ to a colouring $c'$ of $G\setminus\{v,v_2\}$, and extend this to a nice colouring of $G$. First we assign colour $2$ to $v$. This produces a proper partial colouring which is odd at $v_4$ and $v_5$. The vertices of $N(v_2)\setminus\{v\}$ have colours $1,1,3,3,2'$, so after colouring $v$, we have that $v$ is the only neighbour of $v_2$ with colour $2$, and hence the colouring is odd at $v_2$. In addition, there are $4$ colours forbidden at $v_2$ by properness, and since $v$ and $x$ have odd degree, there are at most $4$ colours forbidden by oddness. Hence there is a colour left over, which we use to colour $v_2$. This completes the proof for the case $\delta(G) = 5$.

§ THE CASE $\DELTA(G) = 6$

We are now left with the case $\delta(G) = 6$, which, as discussed earlier, corresponds to the case where $G$ is a $6$-regular triangulation of the torus. Such triangulations were classified by Altshuler [1]. We will use the notation of Balachandran and Sankarnarayanan [2]. For $m, n \geq 1$ and $0 \leq t < n$, we define the graph $H = T(m,n,t)$ on vertex set $V(H) = \{(i,j): 1 \leq i \leq m, 1 \leq j \leq n\}$ as follows:

* $(i,j) \sim (i,j+1)$ for all $i,j$,

* $(i,j) \sim (i+1,j),(i+1,j-1)$ for $1 \leq i < m$ and all $j$,

* $(m,j) \sim (1,j-t),(1,j-t-1)$ for all $j$.

The addition in the second co-ordinate is modulo $n$ above and throughout this section.

In other words, we begin with a grid graph of dimensions $(m+1) \times (n+1)$ and triangulate it. We then identify the top and bottom rows, and we identify the leftmost and rightmost columns with a shift of $t$ vertices.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=.15cm, fill=black
(1,1) grid (5,7);
in 1,...,5
in 1,...,7
[enclosed] () at (,) ;

in 1,...,6
[left] at (1,) (1,);

in 2,3,4
[below] at (,1) (,1);
[above] at (,7) (,1);

[left] at (1,7) (1,1);
[right] at (5,1) (1,3);
[right] at (5,2) (1,4);
[right] at (5,3) (1,5);
[right] at (5,4) (1,6);
[right] at (5,5) (1,1);
[right] at (5,6) (1,2);
[right] at (5,7) (1,3);

(2,1) – (1,2);
(3,1) – (1,3);
(4,1) – (1,4);
(5,1) – (1,5);
(5,2) – (1,6);
(5,3) – (1,7);
(5,4) – (2,7);
(5,5) – (3,7);
(5,6) – (4,7);

A diagram of $T(4,6,4)$. The first row and column are shown twice.

Note that two graphs $T(m,n,t)$ and $T(m',n',t')$ with different parameters can be isomorphic, and that this construction does not always produce a simple graph, although we are only concerned with the cases where it does.

Every $6$-regular triangulation of the torus is isomorphic to $T(m,n,t)$ for some $m,n,t$.

To finish the proof of Theorem <ref>, it therefore suffices to prove that every $T(m,n,t)$ that is a simple graph admits an odd colouring with at most $9$ colours. We do not claim that this is optimal; indeed, we believe that with more care it should be possible to show that $7$ colours will always suffice. We will consider three cases: $m \geq 3$, $m=2$ and $m=1$. Note that we must have $n \geq 3$, or $T(m,n,t)$ would not be simple.

We will find it useful to partition the $9$ available colours into three classes $C_1 = \{1,2,3\}$, $C_2 = \{4,5,6\}$, $C_3 = \{7,8,9\}$. In diagrams, the colours of $C_1$ will be represented by three shades of red, with $1$ being darkest and $3$ lightest. Similarly, $C_2$ will be represented by three shades of blue, and $C_3$ by three shades of green.

§.§ $m \geq 3$

We begin by using only one colour class in each column: in column $i$ we will use the class $C_r$ where $r \equiv i \pmod 3$, unless $m \equiv 1 \pmod 3$, in which case we will use $C_2$ in column $m$. This ensures that the same class of colours is not used in two neighbouring columns. We call a column bad if its two neighbouring columns use the same class; otherwise it is good. If $m \equiv 0 \pmod 3$ then there are no bad columns. If $m \equiv 1 \pmod 3$ then columns $1$ and $m-1$ are bad, and if $m \equiv 2 \pmod 3$ then columns $1$ and $m$ are bad.

Next, we apply the same construction within each column: we colour $(i,j)$ with the colour $s$ in the correct class that satisfies $s \equiv j \pmod 3$, unless $n \equiv 1 \pmod 3$, in which case we use the colour with $s \equiv 2 \pmod 3$ at $(i,n)$. We call the resulting colouring $c$; note that this initial colouring does not depend on the value of $t$. Again, we call a row bad if its two neighbouring rows use the same set of colours; otherwise it is good. The same classification of bad rows applies as for bad columns, according to the value of $n$ modulo $3$.

This construction clearly produces a proper colouring, since $n \geq 3$. In addition, for any vertex $(i,j)$ that is not in a bad column, the colours of $(i+1,j)$ and $(i+1,j-1)$ appear exactly once in its neighbourhood. If $(i,j)$ is in a bad column but not in a bad row, then the colours of $(i,j+1)$ and $(i,j-1)$ appear exactly once in its neighbourhood. Therefore the only vertices at which the colouring $c$ may not be odd are those that are both in a bad column and a bad row. These only exist if neither $m$ nor $n$ is $0 \pmod 3$, and in that case there are exactly $4$ of them. We call these bad vertices.

First consider the case where $m$ and $n$ are both $1 \pmod 3$. Columns $1$ and $m-1$ and rows $1$ and $n-1$ are bad. Now, for each bad vertex $v = (i,j)$, its neighbour $w = (i+1,j-1)$ is in a good column. Therefore the two neighbours of $w$ in column $i+2$ use colours from the one class that is not used at $v$ or $w$. There is thus one colour in this class that does not appear in $c(N(w))$, and we now recolour $w$ with that colour. We do this for all four bad vertices, creating a new colouring $c'$. Let $S$ be the set consisting of the four recoloured vertices. By construction, $c'$ is a proper colouring, since none of the four vertices of $S$ are adjacent.

col1/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!100
col2/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!50
col3/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!20
col4/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!100
col5/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!50
col6/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!20
col7/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!100
col8/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!50
col9/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!20

in 1,...,7
[left,xshift=-1mm] at (1,) (1,);

in 3,...,7
[right,xshift=1mm] at (8,-2) (1,);

in 1,2,3
[right,xshift=1mm] at (8,+5) (1,);

[left,xshift=-1mm] at (1,8) (1,1);
in 2,...,7
[below,yshift=-1mm] at (,1) (,1);
[above,yshift=1mm] at (,8) (,1);

(1,1) grid (8,8);
(2,1) – (1,2);
(3,1) – (1,3);
(4,1) – (1,4);
(5,1) – (1,5);
(6,1) – (1,6);
(7,1) – (1,7);
(8,1) – (1,8);
(8,2) – (2,8);
(8,3) – (3,8);
(8,4) – (4,8);
(8,5) – (5,8);
(8,6) – (6,8);
(8,7) – (7,8);

(2,5) circle (0.35);
(2,7) circle (0.35);
(7,5) circle (0.35);
(7,7) circle (0.35);

[col1] () at (1,1) ;
[col1] () at (1,4) ;
[col1] () at (1,8) ;
[col2] () at (1,2) ;
[col2] () at (1,5) ;
[col2] () at (1,7) ;
[col3] () at (1,3) ;
[col3] () at (1,6) ;
[col4] () at (2,1) ;
[col4] () at (2,4) ;
[col4] () at (2,8) ;
[col5] () at (2,2) ;
[col9] () at (2,5) ;
[col7] () at (2,7) ;
[col6] () at (2,3) ;
[col6] () at (2,6) ;
[col7] () at (3,1) ;
[col7] () at (3,4) ;
[col7] () at (3,8) ;
[col8] () at (3,2) ;
[col8] () at (3,5) ;
[col8] () at (3,7) ;
[col9] () at (3,3) ;
[col9] () at (3,6) ;
[col1] () at (4,1) ;
[col1] () at (4,4) ;
[col1] () at (4,8) ;
[col2] () at (4,2) ;
[col2] () at (4,5) ;
[col2] () at (4,7) ;
[col3] () at (4,3) ;
[col3] () at (4,6) ;
[col4] () at (5,1) ;
[col4] () at (5,4) ;
[col4] () at (5,8) ;
[col5] () at (5,2) ;
[col5] () at (5,5) ;
[col5] () at (5,7) ;
[col6] () at (5,3) ;
[col6] () at (5,6) ;
[col7] () at (6,1) ;
[col7] () at (6,4) ;
[col7] () at (6,8) ;
[col8] () at (6,2) ;
[col8] () at (6,5) ;
[col8] () at (6,7) ;
[col9] () at (6,3) ;
[col9] () at (6,6) ;
[col4] () at (7,1) ;
[col4] () at (7,4) ;
[col4] () at (7,8) ;
[col5] () at (7,2) ;
[col1] () at (7,5) ;
[col3] () at (7,7) ;
[col6] () at (7,3) ;
[col6] () at (7,6) ;
[col1] () at (8,6) ;
[col1] () at (8,2) ;
[col2] () at (8,7) ;
[col2] () at (8,3) ;
[col2] () at (8,5) ;
[col3] () at (8,1) ;
[col3] () at (8,4) ;
[col3] () at (8,8) ;

The case $m \equiv 1 \pmod 3$, $n \equiv 1 \pmod 3$, illustrated by $T(7,7,5)$. The vertices of $S$ are circled.

We now need to check that $c'$ is an odd colouring. First, observe that $c$ is odd at any vertex that has no neighbours in $S$, and therefore $c'$ is also odd at all such vertices. Note that in $c$, every vertex has an even number of neighbours in each colour class $C_i$. Therefore any vertex $v$ that is adjacent to exactly one vertex of $S$ has an odd number of neighbours in some colour class, and therefore $c'$ is odd at $v$.

There is no vertex adjacent to more than two vertices in $S$, so we are left to consider vertices with exactly two neighbours in $S$. There are two types of such vertices. First, there are vertices $v$ in bad columns with one neighbour in $S$ in each adjacent column. But then $v$ has exactly three neighbours in its own colour class in $c'$, so $c'$ is odd at $v$. Secondly, there are vertices $v = (i,j)$ in good columns where both $(i,j+1)$ and $(i,j-1)$ are in $S$. But in this case column $i-1$ is bad, and the two neighbours of $v$ in this column have distinct colours, each of which only appears once in $N(v)$. Thus $c'$ is an odd colouring.

Next we have the case $m \equiv 1 \pmod 3$, $n \equiv 2 \pmod 3$. The bad rows are rows $1$ and $n$, so $u = (2,n)$ is adjacent to the two bad vertices in column $1$ and $w = (m,n)$ is adjacent to the two bad vertices in column $m-1$. We recolour each of these vertices similarly to the previous case: we assign colour $9$ to $u$ since $9 \notin c(N(u))$, and recolour $w$ with whichever colour in $C_1$ does not appear in $c(N(w))$. This produces a proper colouring $c'$. The proof that $c'$ is an odd colouring proceeds just as in the $n \equiv 1 \pmod 3$ case, though it is simpler since only a vertex in a bad column can be adjacent to both $u$ and $v$.

col1/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!100
col2/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!50
col3/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!20
col4/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!100
col5/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!50
col6/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!20
col7/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!100
col8/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!50
col9/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!20

in 1,...,5
[left,xshift=-1mm] at (1,) (1,);

in 3,...,5
[right,xshift=1mm] at (8,-2) (1,);

in 1,2,3
[right,xshift=1mm] at (8,+3) (1,);

[left,xshift=-1mm] at (1,6) (1,1);
in 2,...,7
[below,yshift=-1mm] at (,1) (,1);
[above,yshift=1mm] at (,6) (,1);

(1,1) grid (8,6);
(2,1) – (1,2);
(3,1) – (1,3);
(4,1) – (1,4);
(5,1) – (1,5);
(6,1) – (1,6);
(7,1) – (2,6);
(8,1) – (3,6);
(8,2) – (4,6);
(8,3) – (5,6);
(8,4) – (6,6);
(8,5) – (7,6);

(2,5) circle (0.35);
(7,5) circle (0.35);

[col1] at (1,1) ;
[col1] at (1,4) ;
[col1] at (1,6) ;
[col2] at (1,2) ;
[col2] at (1,5) ;
[col3] at (1,3) ;
[col4] at (2,1) ;
[col4] at (2,4) ;
[col4] at (2,6) ;
[col5] at (2,2) ;
[col9] at (2,5) ;
[col6] at (2,3) ;
[col7] at (3,1) ;
[col7] at (3,4) ;
[col7] at (3,6) ;
[col8] at (3,2) ;
[col8] at (3,5) ;
[col9] at (3,3) ;
[col1] at (4,1) ;
[col1] at (4,4) ;
[col1] at (4,6) ;
[col2] at (4,2) ;
[col2] at (4,5) ;
[col3] at (4,3) ;
[col4] at (5,1) ;
[col4] at (5,4) ;
[col4] at (5,6) ;
[col5] at (5,2) ;
[col5] at (5,5) ;
[col6] at (5,3) ;
[col7] at (6,1) ;
[col7] at (6,4) ;
[col7] at (6,6) ;
[col8] at (6,2) ;
[col8] at (6,5) ;
[col9] at (6,3) ;
[col4] at (7,1) ;
[col4] at (7,4) ;
[col4] at (7,6) ;
[col5] at (7,2) ;
[col3] at (7,5) ;
[col6] at (7,3) ;
[col1] at (8,4) ;
[col1] at (8,2) ;
[col2] at (8,5) ;
[col2] at (8,3) ;
[col3] at (8,1) ;
[col3] at (8,6) ;

The case $m \equiv 1 \pmod 3$, $n \equiv 2 \pmod 3$, illustrated by $T(7,5,3)$. The two recoloured vertices $u$ and $w$ are circled.

We now move on to $m \equiv 2 \pmod 3$, with bad columns $1$ and $m$. Suppose that $n \equiv 1 \pmod 3$, so that rows $1$ and $n-1$ are bad. We recolour vertices as follows: $c'((2,n)) = c'((m-1,2)) = 7$, $c'((2,n-2)) = c'((m-1,n)) = 9$. Elsewhere $c' = c$. Let the set of recoloured vertices be $S$. This creates a proper colouring, and the proof that $c'$ is odd runs the same as in the previous cases, but with one additional detail: if $m = 5$ then it is possible for a vertex $v$ in column $3$ to have two neighbours in $S$, one in column $2$ and one in column $4$. However, in this case, $v$ has exactly one neighbour in colour class $C_1$ and one in class $C_2$, so $c'$ is odd at $v$.

col1/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!100
col2/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!50
col3/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!20
col4/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!100
col5/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!50
col6/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!20
col7/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!100
col8/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!50
col9/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!20

in 1,...,7
[left,xshift=-1mm] at (1,) (1,);

in 3,...,7
[right,xshift=1mm] at (6,-2) (1,);

in 1,2,3
[right,xshift=1mm] at (6,+5) (1,);

[left,xshift=-1mm] at (1,8) (1,1);
in 2,...,5
[below,yshift=-1mm] at (,1) (,1);
[above,yshift=1mm] at (,8) (,1);

(1,1) grid (6,8);
(2,1) – (1,2);
(3,1) – (1,3);
(4,1) – (1,4);
(5,1) – (1,5);
(6,1) – (1,6);
(6,2) – (1,7);
(6,3) – (1,8);
(6,4) – (2,8);
(6,5) – (3,8);
(6,6) – (4,8);
(6,7) – (5,8);

(2,5) circle (0.35);
(2,7) circle (0.35);
(4,2) circle (0.35);
(4,7) circle (0.35);

[col1] () at (1,1) ;
[col1] () at (1,4) ;
[col1] () at (1,8) ;
[col2] () at (1,2) ;
[col2] () at (1,5) ;
[col2] () at (1,7) ;
[col3] () at (1,3) ;
[col3] () at (1,6) ;
[col4] () at (2,1) ;
[col4] () at (2,4) ;
[col4] () at (2,8) ;
[col5] () at (2,2) ;
[col9] () at (2,5) ;
[col7] () at (2,7) ;
[col6] () at (2,3) ;
[col6] () at (2,6) ;
[col7] () at (3,1) ;
[col7] () at (3,4) ;
[col7] () at (3,8) ;
[col8] () at (3,2) ;
[col8] () at (3,5) ;
[col8] () at (3,7) ;
[col9] () at (3,3) ;
[col9] () at (3,6) ;
[col1] () at (4,1) ;
[col1] () at (4,4) ;
[col1] () at (4,8) ;
[col7] () at (4,2) ;
[col2] () at (4,5) ;
[col9] () at (4,7) ;
[col3] () at (4,3) ;
[col3] () at (4,6) ;
[col4] () at (5,1) ;
[col4] () at (5,4) ;
[col4] () at (5,8) ;
[col5] () at (5,2) ;
[col5] () at (5,5) ;
[col5] () at (5,7) ;
[col6] () at (5,3) ;
[col6] () at (5,6) ;
[col1] () at (6,6) ;
[col1] () at (6,2) ;
[col2] () at (6,7) ;
[col2] () at (6,3) ;
[col2] () at (6,5) ;
[col3] () at (6,1) ;
[col3] () at (6,4) ;
[col3] () at (6,8) ;

The case $m \equiv 2 \pmod 3$, $n \equiv 1 \pmod 3$, illustrated by $T(5,7,5)$. The vertices of $S$ are circled.

Finally, we have the case $m \equiv 2 \pmod 3$, $n \equiv 2 \pmod 3$. Now rows $1$ and $n$ are bad. We recolour $c'((2,n)) = c'((m-1,1)) = 9$ and otherwise leave $c$ unchanged. Once again, $c'$ is proper, and the proof that it is odd is the same as in the previous case. This completes the proof that $T(m,n,t)$ has a nice colouring for $m \geq 3$.

col1/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!100
col2/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!50
col3/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!20
col4/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!100
col5/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!50
col6/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!20
col7/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!100
col8/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!50
col9/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!20

in 1,...,5
[left,xshift=-1mm] at (1,) (1,);

in 3,...,5
[right,xshift=1mm] at (6,-2) (1,);

in 1,2,3
[right,xshift=1mm] at (6,+3) (1,);

[left,xshift=-1mm] at (1,6) (1,1);
in 2,3,5
[below,yshift=-1mm] at (,1) (,1);
[above,yshift=1mm] at (,6) (,1);

[below,yshift=-2mm] at (4,1) (4,1);
[above,yshift=2mm] at (4,6) (4,1);

(1,1) grid (6,6);
(2,1) – (1,2);
(3,1) – (1,3);
(4,1) – (1,4);
(5,1) – (1,5);
(6,1) – (1,6);
(6,2) – (2,6);
(6,3) – (3,6);
(6,4) – (4,6);
(6,5) – (5,6);

(2,5) circle (0.35);
(4,1) circle (0.35);
(4,6) circle (0.35);

[col1] at (1,1) ;
[col1] at (1,4) ;
[col1] at (1,6) ;
[col2] at (1,2) ;
[col2] at (1,5) ;
[col3] at (1,3) ;
[col4] at (2,1) ;
[col4] at (2,4) ;
[col4] at (2,6) ;
[col5] at (2,2) ;
[col9] at (2,5) ;
[col6] at (2,3) ;
[col7] at (3,1) ;
[col7] at (3,4) ;
[col7] at (3,6) ;
[col8] at (3,2) ;
[col8] at (3,5) ;
[col9] at (3,3) ;
[col9] at (4,1) ;
[col1] at (4,4) ;
[col9] at (4,6) ;
[col2] at (4,2) ;
[col2] at (4,5) ;
[col3] at (4,3) ;
[col4] at (5,1) ;
[col4] at (5,4) ;
[col4] at (5,6) ;
[col5] at (5,2) ;
[col5] at (5,5) ;
[col6] at (5,3) ;
[col1] at (6,4) ;
[col1] at (6,2) ;
[col2] at (6,5) ;
[col2] at (6,3) ;
[col3] at (6,1) ;
[col3] at (6,6) ;

The case $m \equiv 2 \pmod 3$, $n \equiv 2 \pmod 3$, illustrated by $T(5,5,3)$. The two recoloured vertices are circled; note that $(4,1)$ is shown twice.

§.§ $m = 2$

We begin by colouring the vertices as in the $m \geq 3$ case: we use colours $\{1,2,3\}$ for column $1$ and $\{4,5,6\}$ for column 2, and $(i,j)$ is assigned the colour in the corresponding class that is equivalent to $j \pmod 3$, unless $n \equiv 1 \pmod 3$ in which case $(1,n)$ and $(2,n)$ receive colours $2$ and $5$ respectively. Let this colouring be $c$.

In the terminology of the $m \geq 3$ case, both columns are bad and there are at most two bad rows. If bad rows exist, then we can choose two good vertices $u$ and $w$ such that every bad vertex is adjacent to at least one of $u$ and $w$. We then recolour by using colours $7$ and $8$ at $u$ and $w$ respectively to create a new colouring $c'$. This colouring is trivially proper. It is also odd, since $c$ is odd at every vertex that is not adjacent to $u$ or $w$, and for every vertex that is adjacent to $u$ or $w$, either $7$ or $8$ appears exactly once in its neighbourhood in $c'$.

col1/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!100
col2/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!50
col3/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!20
col4/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!100
col5/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!50
col6/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!20
col7/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!100
col8/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!50
col9/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!20

(1,1) grid (3,6);
(2,1) – (1,2);
(3,1) – (1,3);
(3,2) – (1,4);
(3,3) – (1,5);
(3,4) – (1,6);
(3,5) – (2,6);

(1,2) circle (0.35);
(2,5) circle (0.35);
(3,4) circle (0.35);

in 1,3,4,5
[left,xshift=-1mm] at (1,) (1,);

[left,xshift=-2.5mm] at (1,2) (1,2);
[left,xshift=-1mm] at (1,6) (1,1);
[below,yshift=-1mm] at (2,1) (2,1);
[above,yshift=1mm] at (2,6) (2,1);
in 1,3,4
[right,xshift=1mm] at (3,+2) (1,);

[right,xshift=2.5mm] at (3,4) (1,2);
[right,xshift=1mm] at (3,1) (1,4);
[right,xshift=1mm] at (3,2) (1,5);

[col1] at (1,1) ;
[col1] at (1,4) ;
[col1] at (1,6) ;
[col7] at (1,2) ;
[col2] at (1,5) ;
[col3] at (1,3) ;
[col4] at (2,1) ;
[col4] at (2,4) ;
[col4] at (2,6) ;
[col5] at (2,2) ;
[col8] at (2,5) ;
[col6] at (2,3) ;
[col1] at (3,3) ;
[col1] at (3,6) ;
[col1] at (3,1) ;
[col7] at (3,4) ;
[col2] at (3,2) ;
[col3] at (3,5) ;

$T(2,5,2)$ coloured as above. The two recoloured vertices are circled; note that $(1,2)$ is shown twice.

§.§ $m = 1$

Let $H = T(1,n,t)$. We will refer to vertex $(1,j)$ as just $j$ for simplicity. Thus $j$ is adjacent to $j\pm 1$, $j \pm t$ and $j \pm (t+1)$, working modulo $n$. We can now see that $T(1,n,t)$ is isomorphic to $T(1,n,n-(t+1))$, and so $t < \f{n}{2}$ without loss of generality. Let $r = \left\lceil\f{n}{t}\right\rceil$, so that by the above we have $r \geq 3$. Note also that $t \geq 2$, otherwise the graph $T(1,n,t)$ would not be simple.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=1.5mm, fill=black

in 1,...,13
[red] (360*/13+90:3cm) – (360*4/13+360*/13+90:3cm);
[blue] (90+360*/13:3cm) – (90+360*5/13+360*/13:3cm);
at (90+360*/13:3.35cm) ;
[enclosed] (v) at (90+360*/13:3cm) ;

(0,0) circle (3);

The graph $T(1,13,4)$. Edges $j \sim (j \pm 4)$ are shown in red and edges $j \sim (j \pm 5)$ in blue.

Now we partition the vertices of $T(1,n,t)$ into intervals: for $1 \leq k \leq \left\lfloor\f{n}{t}\right\rfloor$, let $I_k = \{j: (k-1)t+1 \leq j \leq kt\}$, and if $n$ is not a multiple of $t$, then $I_r = \{j: kt+1 \leq j \leq n\}$ consists of the remaining vertices. There are $r$ intervals in total.

As in the case $m \geq 3$, we split the colours into classes $C_1 = \{1,2,3\}$, $C_2 = \{4,5,6\}$ and $C_3 = \{7,8,9\}$. For each $C_i$ we now define the set of vertices $S_i$ at which $C_i$ will be used.

* If $r \equiv 0 \pmod 3$, then $S_i = \cup_{k \equiv i \pmod 3}I_k$.

* If $r \equiv 1 \pmod 3$, then the $S_i$ are defined as for the $0 \pmod 3$ case except that $I_r$ is part of $S_2$ instead of $S_1$.

* If $r \equiv 2 \pmod 3$, then the $S_i$ are defined as for the $0 \pmod 3$ case except that $I_{r-1}$ is part of $S_2$ and $I_r$ is part of $S_3$.

(0,0) circle (1.5);
(-4.5,0) circle (1.5);
(4.5,0) circle (1.5);

(-4.5,0) +(90:1.3) – +(90:1.7) +(190:1.3) – +(190:1.7) +(290:1.3) – +(290:1.7) +(30:1.3) – +(30:1.7);
(A) at (-4.5,0) ;
(A) ++(140:1.2) node () $I_1$;
(A) ++(240:1.2) node () $I_2$;
(A) ++(340:1.2) node () $I_3$;
(A) ++(60:1.2) node () $I_4$;
(A) ++(140:1.8) node () $S_1$;
(A) ++(240:1.8) node () $S_2$;
(A) ++(340:1.8) node () $S_3$;
(A) ++(60:1.8) node () $S_2$;
at (-4.5,-2.2) $r \equiv 1 \pmod 3$;

(90:1.3) – (90:1.7) (170:1.3) – (170:1.7) (250:1.3) – (250:1.7) (330:1.3) – (330:1.7) (50:1.3) – (50:1.7);
at (130:1.2) $I_1$;
at (210:1.2) $I_2$;
at (290:1.2) $I_3$;
at (10:1.2) $I_4$;
at (70:1.2) $I_5$;
at (130:1.8) $S_1$;
at (210:1.8) $S_2$;
at (290:1.8) $S_3$;
at (10:1.8) $S_2$;
at (70:1.8) $S_3$;
at (0,-2.2) $r \equiv 2 \pmod 3$;

(4.5,0) +(90:1.3) – +(90:1.7) +(155:1.3) – +(155:1.7) +(220:1.3) – +(220:1.7) +(285:1.3) – +(285:1.7) +(350:1.3) – +(350:1.7) +(55:1.3) – +(55:1.7);
(B) at (4.5,0) ;
(B) ++(122.5:1.2) node () $I_1$;
(B) ++(187.5:1.2) node () $I_2$;
(B) ++(252.5:1.2) node () $I_3$;
(B) ++(317.5:1.2) node () $I_4$;
(B) ++(22.5:1.2) node () $I_5$;
(B) ++(72.5:1.2) node () $I_6$;
(B) ++(122.5:1.8) node () $S_1$;
(B) ++(187.5:1.8) node () $S_2$;
(B) ++(252.5:1.8) node () $S_3$;
(B) ++(317.5:1.8) node () $S_1$;
(B) ++(22.5:1.8) node () $S_2$;
(B) ++(72.5:1.8) node () $S_3$;
at (4.5,-2.2) $r \equiv 0 \pmod 3$;

The partition of $T(1,n,t)$ into intervals $I_i$ and subsets $S_i$. As in Figure <ref>, the graph is depicted as a circle.

We now consider the induced graphs $H[S_i]$. The construction above ensures that the only edges between two vertices in the same interval are edges of the form $\{j,j+1\}$. In addition, the only edges between two distinct intervals in the same $S_i$ are edges of the form $\{kt,(k+1)t+1\}$ between the last vertex of one interval and the first vertex of another. This means that the induced graphs $H[S_i]$ are unions of disjoint paths, with the exception of the case $r = 4$, when $H[S_2]$ is a cycle. A path clearly has a proper odd $3$-colouring, so if $r \neq 4$ we can use the colours of $C_i$ to colour the vertices of each $S_i$ such that a proper odd colouring is induced on $H[S_i]$. This produces a nice colouring of $H$.

enclosed/.style=draw, circle, inner sep=0pt, minimum size=1.5mm, fill=black
col1/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!100
col2/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!50
col3/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Mahogany!20
col4/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!100
col5/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!50
col6/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=Blue!20
col7/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!100
col8/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!50
col9/.style=fill, circle, inner sep=0pt, minimum size=3mm, color=OliveGreen!20

in 1,...,13
at (90+360*/13:3.4) ;
[Gray!50] (360*/13+90:3cm) – (360*4/13+360*/13+90:3cm);
[Gray!50] (90+360*/13:3cm) – (90+360*5/13+360*/13:3cm);

(90+1*360/13:3) arc (90+1*360/13:90+4*360/13:3);
(90+5*360/13:3) arc (90+5*360/13:90+8*360/13:3);
(90-4*360/13:3) arc (90-4*360/13:90-1*360/13:3);
[Gray!50] (90+4*360/13:3) arc (90+4*360/13:90+5*360/13:3);
[Gray!50] (90+8*360/13:3) arc (90+8*360/13:90+9*360/13:3);
[Gray!50] (90-1*360/13:3) arc (90-1*360/13:90+1*360/13:3);
[col1] at (90+1*360/13:3) ;
[col2] at (90+2*360/13:3) ;
[col3] at (90+3*360/13:3) ;
[col1] at (90+4*360/13:3) ;
[col4] (v5) at (90+5*360/13:3) ;
[col5] at (90+6*360/13:3) ;
[col6] at (90+7*360/13:3) ;
[col5] (v8) at (90+8*360/13:3) ;
[col7] at (90+9*360/13:3) ;
[col8] at (90-3*360/13:3) ;
[col9] at (90-2*360/13:3) ;
[col7] at (90-1*360/13:3) ;
[col6] (v13) at (90:3) ;
at (90+2.5*360/13:3.8) $S_1$;
at (90+6.5*360/13:3.8) $S_2$;
at (90-2.5*360/13:3.8) $S_3$;

(v5) – (v13) – (v8);

$T(1,13,4)$ coloured as below. Edges within the same $S_i$ are shown in black and edges between different $S_i$ in grey.

We are left with the case $r = 4$, where $3t+1 \leq n \leq 4t$. We begin by colouring the vertices of $S_1$ and $S_3$ using $C_1$ and $C_3$ respectively as in the previous case. Recall that $S_2$ consists of the union of $I_2 = \{j: t+1 \leq j \leq 2t\}$ and $I_4 = \{j: 3t+1 \leq j \leq n\}$. We properly $3$-colour the cycle $H[S_2]$ and apply the resulting colouring in $H$, giving no regard to oddness for the time being.

For $t+2 \leq j \leq 2t$, vertex $j$ is adjacent to exactly two vertices in $I_1$, and these are adjacent to each other and thus receive different colours from $C_1$. The colouring is therefore odd at $j$ for $t+2 \leq j \leq 2t$. Since $t \geq 2$, the same argument can be applied to vertex $t+1$ and interval $I_3$, showing that the colouring is odd at $j = t+1$ and therefore at every vertex in $I_2$.

If $n \geq 3t+2$, we can repeat this argument to show that the colouring is odd at every vertex of $I_4$, and therefore we have found a nice colouring of $H$. If instead $n = 3t+1$ then the argument breaks down at vertex $3t+1$. However, we know that the cycle $H[S_2]$ can be properly $3$-coloured in such a way that there are at most two vertices at which the colouring is not odd: indeed we made heavy use of the necessary constructions in the case $m \geq 3$. Clearly we can ensure that vertex $3t+1$ is not one of these vertices. Thus the colouring of $H[S_2]$ is odd at $3t+1$, and therefore the resulting colouring of $H$ is also odd at $3t+1$. This completes the proof of Theorem <ref>.

§ CONCLUSION

First, we note that the proof of Theorem <ref> also works for the real projective plane. Since the projective plane has Euler characteristic $1$, Euler's formula tells us that any graph $G$ on the projective plane has $\delta(G) \leq 5$, and that the total charge over all vertices and faces of $G$ in the discharging process is at most $-6$. Thus the discharging method alone suffices, and there is no special case such as the one dealt with in Section <ref>. We did not use any other properties of the torus that do not also hold for the real projective plane: like the torus, the projective plane is locally homeomorphic to the Euclidean plane, and orientation did not matter anywhere in our discharging proof. We therefore have the following result.

Let $G$ be a simple graph that embeds in the real projective plane. Then $G$ has a proper odd colouring with at most $9$ colours.

For a surface $S$, let $\chi_o(S)$ denote the maximum value of $\chi_o(G)$ over all simple graphs that can be embedded in $S$. We have therefore shown that for the torus $T$,
$$7 \leq \chi_o(T) \leq 9.$$

We believe that in fact $7$ colours will always suffice.

Let $G$ be a toroidal graph. Then $\chi_o(G) \leq 7$.

Improving the upper bound beyond $9$ will likely require a new approach. Note that the two proofs that $8$ colours suffice for planar graphs, by Petr and Portier [5] and Fabrici et al. [3], both use the Four Colour Theorem, and the bound of $8$ arises specifically as twice the bound of $4$ for ordinary colourings.

The same methods applied to the torus would only produce an upper bound of $14$ colours for odd colourings. Indeed, we obtain a bound of $\chi_o(S) \leq 2\chi(S)$ for a general surface $S$, where $\chi(S)$ is the maximum of $\chi(G)$ over all graphs that embed in $S$. Any improvement on this bound for general surfaces $S$ would be of interest. In particular, it is natural to ask the following:

Does $\chi(S) = \chi_o(S)$ for every surface other than the plane?

§ ACKNOWLEDGEMENTS

The author would like to thank his PhD supervisor Professor Béla Bollobás for his helpful comments, and Jan Petr and Julien Portier for introducing him to the topic and for their encouragement.

[1]
A. Altshuler. Construction and enumeration of regular maps on the torus. Discrete Math. 4 (1973), 201–217.

[2]
N. Balachandran and B. Sankarnarayanan. The choice number versus the chromatic number for graphs embeddable on orientable surfaces. Electron. J. Comb. 28 (2021), #P4.50.

[3]
I. Fabrici, B. Lužar, S. Rindošová, and R. Soták. Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods. arXiv:2202.02570.

[4]
B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, 2001.

[5]
J. Petr and J. Portier. The odd chromatic number of a planar graph is at most 8. arXiv:2201.12381.

[6]
M. Petruševski and R. Škrekovski. Colorings with neighborhood parity condition. arXiv:2112.13710.