FOUR-COLORING SIX-REGULAR GRAPHS ON THE TORUS

KAREN L. COLLINS AND JOAN P. HUTCHINSON

Dedicated to Herbert S. Wilf in honor of his 65th birthday, and to Phyllis Cassidy in honor of her retirement from Smith College.

1. Introduction

A classic 3-color theorem attributed to Heawood [10, 11] (also observed by Kempe [16]) states that every even triangulation of the plane is 3-chromatic; by even we mean that every vertex has even degree. We are interested in the extent to which an analogous theorem carries over to even triangulations of the torus and to other surfaces of larger genus. In general, even triangulations of the torus, like K_{7} and those containing K_{4}, are not 3-colorable, but it turns out that 4-coloring is very often possible.

It is known that the problem of determining 3-colorable graphs on the plane is an NP-complete problem (see [8]), and so 3-color theorems like those for triangle-free planar graphs and their generalizations have been highly prized; for surveys, see [15, 21, 22]. We concern ourselves instead with even triangulations, and we speculate that determining the chromatic number of such triangulations of higher-genus surfaces, including the torus, will yield good theorems. In general the chromatic number of even triangulations can grow with the genus, since for infinitely many values of n, the complete graph K_{n} can triangulate a surface (this follows from the genus formula for K_{n} [19]). The edge-width of such embeddings (i.e., the length of the shortest noncontractible cycle) is always three. Therefore we are interested in even triangulations with edge-width at least four, or even triangulations where the edge-width is an increasing function of the genus of the embedding surface.

This idea of looking at graphs embedded with large edge-width has been a fruitful one, especially for determining the chromatic properties of such graphs, see [24, 26, 27]. For a general graph embedded on an orientable surface of genus g > 0, ⌊\frac{7+\sqrt{48g+1}}{2}⌋ colors are necessary and sufficient [10, 19]; however, Thomassen [26] has shown that a graph embedded on an orientable surface of genus g > 0 can be 5-colored provided all noncontractible cycles have length at least 2^{(14g+5)}. This result was first shown for the torus in [3]. Hence these large edge-width graphs do not differ greatly in chromatic number from planar graphs, which can be 4-colored [5, 20].

Another example of a planar k-coloring theorem with a companion (k + 1)-coloring theorem for the same class of graphs embedded on surfaces, but with large edge-width, is the following. Call graphs that can be embedded in a surface with each region bounded by an even number of edges evenly embeddable. It is well-known that a planar graph can be 2-colored if and only if it is evenly embeddable in the plane. Also, a graph that is evenly embeddable in an orientable surface of genus g > 0 can be ⌊\frac{5+\sqrt{32g−7}}{2}⌋-colored [12], but if it is embedded with edge-width at least 2^{(3g+5)}, then three colors suffice [13]. The advantage of large edge-width is that the graphs are embedded in a “locally planar” fashion [3]. Thus, we conjecture the following.

Conjecture 1.1. Every graph, embedded on an orientable surface of positive genus as an even triangulation and with edge-width sufficiently large, can be 4-colored.

In this paper we focus on the torus and on ostensibly the most difficult case when the graph is a six-regular triangulation; in [28] Thomassen asks for a characterization of the non-4-colorable, 6-regular graphs on the torus. A theorem of Altshuler [4] shows that every 6regular toroidal graph can be represented as a 6-regular shifted rectangular grid on the torus; see Figure 2. A shift of one is the same as an unshifted grid. This allows us to focus first on 6-regular grids and then to extend our colorings to the shifted grids. We show that:

Theorem 1.2. Let G be a graph embedded in a 6-regular m × n grid on the torus with a shift of i. If m, n ≥ 3, then G can be 4-colored, with a finite number of exceptions. If n = 1 or 2, and m ≥ 3, then there is an n_{i} such that every such graph with at least n_{i} vertices can be 4-colored.

Lemmas 3.1, 3.2, 3.4 and Theorem 3.3 handle the unshifted m × n grids for m, n ≥ 3. Theorem 3.6 provides the 4-coloring for the shifted m × n grids, for 3 ≤ n, m with m, n ≠ 5, omitting some exceptions. Theorem 3.7 enumerates these exceptions. In Theorem 3.8 we show that the m × 2 shifted grids are all 4-colorable for m even, and for m odd can be represented either as a 2m × 1 grid or an m′ × n′ grid with 3 ≤ n′, m′ and 2m = m′n′. The case of m × 1 shifted grids is handled in Theorem 3.9. Hence we obtain our main result. It is only in the 3 ≤ n case that we are able to state a bound on edge-width that insures 4-colorability.

Theorem 1.3. If G is a 6-regular toroidal graph, embedded as an m×n grid of any size shift, with 3 ≤ m, n and with edge-width at least 6, then G can be 4-colored.

By results of [1, 2, 28], 6-regular graphs on the torus with edgewidth at least 4 can be 5-colored; see both [28] and below (see the (m × 1; i) grids in Section 3) for an infinite family of 5-chromatic, 6-regular toroidal graphs, all with edge-width three. There are also sporadic 5-chromatic, 6-regular toroidal triangulations of edge-width at most 5; infinite families of 5-chromatic toroidal triangulations with arbitrarily large edge-width are known as are such graphs with exactly two vertices of odd degree [7].

The previous coloring and embedding questions apply to nonorientable surfaces as well. The chromatic number of all nonorientable surfaces is known [18] as it is for evenly embedded graphs on these surfaces [9, 12]. It is worth noting that though Thomassen’s 5-color theorem carries over to nonorientable surfaces, there are 4-chromatic graphs that evenly embed on the projective plane with all regions 4sided and with arbitrarily long noncontractible cycles [30]. It has recently been shown [14] that there are 5-chromatic even triangulations of the projective plane with arbitrarily large edge-width.

2. Background material

We consider graphs that do not contain loops, but may contain multiple edges; we follow the terminology of [15, 29]. A graph is said to be k-colored (respectively, k-colorable) if each vertex of the graph is (resp., can be) assigned one of k colors so that no two adjacent vertices receive the same color. A graph is k-chromatic if k is the least integer so that the graph is k-colorable.

A graph is planar if it can be drawn in the plane (or equivalently on the surface of the sphere) without edge crossings; a graph embeds on a surface if it can be drawn there without edge crossings. The complement of a graph embedded on a surface is a set of open regions; the maximal connected open regions are called faces of the embedding. An embedding is a triangulation if each face is bounded by exactly three edges. The embedding is called a 2-cell embedding if each of the faces is a simply connected region. Crucial tools in the study of embedded graphs are the following: Euler’s Formula. If a connected graph is embedded in the plane with v vertices, e edges, and f faces, then v − e + f = 2.

Euler-Poincaré Theorem. If a graph has a 2-cell embedding with v vertices, e edges, and f faces on a surface of genus g ≥ 0, then v − e + f = 2 − 2g. Using standard counting arguments one gets the following.

Corollary 2.1. If a multigraph with v vertices and e edges is embedded on a surface of genus g ≥ 0 with each face bounded by at least three edges, then e ≤ 3v + 6(g − 1) with equality if and only if the embedding is a triangulation. The average degree of the graph, 2e/v, is at most 6 + 12(g − 1)/v.

Applying the corollary to the torus where g = 1, we have that in general e ≤ 3v and so the average degree of a toroidal graph is at most 6. The embedding is a triangulation if and only if e = 3v, and then the average degree equals 6. Thus a graph on the torus either contains a vertex of degree less than six, or else the graph is 6-regular and a triangulation.

We use a characterization of 6-regular toroidal graphs, due to Altshuler [4]; a similar approach can be found in [25]. Imagine a rectangular grid of m rows and n columns; we label this by giving each grid point the label (i, j) where i denotes its row and j its column. Then define a 6-regular right-diagonal (unshifted) m×n grid on the torus to be the graph given by the vertex set {(i, j)|1 ≤ i ≤ m, 1 ≤ j ≤ n} where the neighbors of (i, j) are (i, j − 1), (i − 1, j), (i − 1, j + 1), (i, j + 1), (i + 1, j), (i + 1, j − 1) and arithmetic in the first coordinate is modulo m and in the second coordinate modulo n; see Figure 1. These grids give a family of 6-regular toroidal graphs, but not all of them. We call the set of vertices C_{h}(i) := {(i, 1), (i, 2), ..., (i, n)} a horizontal cycle and the set of vertices C_{v}(j) := {(1, j), (2, j), ..., (m, j)} a vertical cycle of the grid.

[figure: (i + 1, j − 1); (i, j − 1); (i − 1, j − 1); (i + 1, j); (i, j); (i − 1, j); (i + 1, j + 1); (i, j + 1); (i − 1, j + 1)]

Figure 1. The neighbors of (i, j).

Now, we define a 6-regular right-diagonal (m × n; k) grid for some k, 1 ≤ k ≤ m, to be the same as defined above except that there is a rotation before the vertices in the nth vertical cycle C_{v}(n) are joined to those in the first, C_{v}(1). Specifically the vertex of C_{v}(n), (i, n), is now adjacent to vertices (i + k − 2, 1) and (i + k − 1, 1) as well as to (i+1, n), (i+1, n−1), (i, n−1), (i−1, n) for i = 1, 2, ..., m. In particular the first vertex of C_{v}(n), (1, n), is now adjacent to (k − 1, 1) and (k, 1) in C_{v}(1) and so a grid with shift 1 is the same as the unshifted grids, defined above. Theorem (Altshuler) [4] Every 6-regular graph on the torus can be represented as a 6-regular right-diagonal m × n shifted grid on the torus.

[figure: (1, 1); (1, 2); (1, 3); (1, j − 1); (1, j); (1, n); (i, 1); (1, 1); (1, 2); (1, 3); (1, j − 1); (1, j); (1, n); (i, 1); (m, 1); (m − 1, 1); (2, 1); (3, 1); (2, n); (3, n); (i + 1, 1); (i − 1, 1)]

Figure 2. An m × n grid with a shift of i.

The parameters m and n may be found as follows: traverse a path in the embedded graph that, upon arriving at a vertex, continues “straight ahead,” that is, takes the edge out that leaves two unused edges on either side of the path. As shown in [4] this process leads to a simple cycle, and we can label the vertices of this cycle (1, 1), (2, 1), …, (m, 1). Next at vertex (1, 1), pick an unused edge on which to begin another straight-ahead path and continue until the original cycle is reached, say at vertex (k, 1) after n vertices, labeled (1, 1), (2, 1), …, (n, 1). Then cutting the torus open along the first cycle and the second path produces an (m×n; k) grid. Note that there is choice in picking the unused edge at (1, 1) so that a graph may be represented as a grid with more than one set of parameters.

3. Toroidal results

In the following, read all first coordinates modulo m and second coordinates modulo n. We begin by showing how some colorings of a vertical (or horizontal) cycle in an m × n grid can be extended in the grid. Suppose that the vertical cycle C_{v}(j) is vertex-colored by ϕ. We can extend ϕ to include the next vertical cycle C_{v}(j + 1) by rotation of the coloring in two ways: Define ϕ_{−1}(i, j + 1) = ϕ(i − 1, j) and ϕ_{2}(i, j + 1) = ϕ(i + 2, j) for all i. (Descriptively, take the coloring on C_{v}(j) and rotate it down one vertex, or up two vertices, and place that rotated coloring on the vertices of C_{v}(j + 1).) These rotations need not be proper colorings; however, we shall show that if every successive triple of colors of ϕ on C_{v}(j) is distinct, then ϕ_{−1} and ϕ_{2} give proper coloring extensions. Similarly a coloring on the horizontal cycle C_{h}(i) can be extended to the next horizontal cycle by one of two horizontal shifts.

Lemma 3.1. Let G be a 6-regular right-diagonal m × n (unshifted) grid on the torus where n is a positive integer, and m ≥ 3. Suppose that the vertical cycle C_{v}(j) of G is 3- or 4-colored so that the colors on each successive triple of vertices are distinct, i.e., for every k, (k − 1, j), (k, j), (k + 1, j) are all colored distinctly. Then ϕ_{−1} (respectively, ϕ_{2}) gives a proper coloring on C_{v}(j) ∪ C_{v}(j + 1) with the coloring on C_{v}(j + 1) having the distinct triple property. In particular if m = n, applying ϕ_{−1} (resp., ϕ_{2}) successively to each of the other n−1 columns of G gives a proper coloring. The same results hold with respect to horizontal cycles.

Proof. Without loss of generality, let ϕ be the coloring of C_{v}(1), and consider the coloring on C_{v}(2) resulting by applying ϕ_{−1}. Then a vertex (i, 2) has neighbors (i−1, 2), (i+1, 2), (i, 1) and (i+1, 1) in C_{v}(1)∩C_{v}(2). The vertices (i−1, 2), (i, 2) and (i+1, 2) form a distinctly colored triple since they received the colors, respectively of (i − 2, 1), (i − 1, 1), and (i, 1). Thus ϕ_{−1} can next be applied to C_{v}(3) and so on. After m = n rotations the coloring will be back to that on C_{v}(1) and the coloring on C_{v}(n) ∪ C_{v}(1) will be proper. The same proof works using ϕ_{2} and with horizontal cycles and their horizontal rotations.

Now we demonstrate a variety of cases to show that if G is an unshifted graph with edge-width at least four, it is 4-colorable. Note that an unshifted m × 1 grid is full of loops and so we don’t color these. The unshifted m × 2 grids are easily understood: in these the vertices of C_{v}(1) and C_{v}(2) form a complete graph on four vertices, and a 4coloring of this complete graph extends to all vertices if and only if m is even. All m × 2 grids are multigraphs, embedded with edge-width two.

Lemma 3.2. Let G be a 6-regular right-diagonal m × 3l grid on the torus, where l is a positive integer and m ≠ 5. Then G is 4-colorable.

Proof. Write m = 3t + 4s where t ≥ 0 and s = 0, 1, 2. Color C_{v}(1) by s successive repetitions of 1 2 3 4 followed by t repetitions of 1 2 3 ; let this be the coloring ϕ. Extend this coloring to C_{v}(2) and C_{v}(3) by applying ϕ_{−1} twice. Since an application of ϕ_{2} to C_{v}(3) returns the coloring to that of C_{v(1)}, this gives a proper coloring of the m × 3 grid by Lemma 3.1, and therefore the coloring of the first m×3 subgrid can be repeated l times to make a proper coloring of the m × 3l grid.

Theorem 3.3. Let G be a 6-regular right-diagonal m × n grid on the torus. Then if m, n ≥ 3, G is 4-colorable.

Proof. The case when one or both of m and n is 5 is handled in the Lemma 3.4 below. We can also assume that n is not divisible by 3 by Lemma 3.2. If n = m, we need only prove that there exists a coloring of an n-cycle in which every set of successive triples is colored distinctly, and then use Lemma 3.1. Write n = 3v + 4u where v ≥ 0 and u = 1, 2. We can do this unless n = 5. Then coloring an n-cycle by u repetitions of 1 2 3 4 and v repetitions of 1 2 3 will ensure that every successive triple is distinct.

Suppose that n > m ≥ 3, and n, m ≠ 5. Write m = 3t + 4s where t ≥ 0 and s = 0, 1, 2. Color the first four vertices in each horizontal cycle of the m × n grid as follows: put in t sets of the three rows

1 2 3 4
3 4 1 2
2 3 4 1

and s sets of the four rows

1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1

One can check that this is a proper coloring of the m×4 grid. Further, the vertical cycle C_{v}(4) has every successive triple colored distinctly; call this coloring ϕ. If n ≡ 1 (mod 3), then apply ϕ_{−1} twice to get a coloring on C_{v}(5) and C_{v}(6). Color C_{v}(7) the same as C_{v}(4). The coloring on the block C_{v}(5), C_{v}(6), C_{v}(7) is then a proper coloring of an m × 3 grid; hence it can be repeated (n − 7)/3 times. This is still a proper coloring of the entire grid, since C_{v}(n) is colored the same as C_{v}(4).

If n ≡ 2 (mod 3), repeat the first block of m × 4 colors to color an m × 8 block. Then let ϕ be the coloring on C_{v}(8) and apply ϕ_{−1} twice to color C_{v}(9) and C_{v}(10), and color C_{v}(11) the same as C_{v}(8). Repeat the C_{v}(9), C_{v}(10), C_{v}(11) block (n − 11)/3 times to finish coloring the grid.

Note that if m > n ≥ 3 (and n, m ≠ 5), then a k-coloring of the n × m grid, as given above, yields a k-coloring of the m × n grid by taking the transpose.

There still remains the case when one or both of m, n is 5; using the transpose argument, we can suppose that m = 5.

Lemma 3.4. Any 5 × n grid is 4-colorable if n ≥ 3.

Proof. The method of distinct successive triples will not work for a 5 × n grid, because every non-adjacent pair of vertices in a 5-cycle is connected by a path of length 2, and in a 3- or 4- coloring of a 5-cycle, at least one color must be used twice. Thus the proof we have is to demonstrate a proper coloring of the 5 × n grid for n = 3, 4, 5, 6, 7, 9, and then show how to construct a coloring of a larger grid from one of these. Here are proper colorings of the 5 × 3, 5 × 4, 5 × 5, 5 × 6, 5 × 7 and 5 × 9 grids.

1 2 3 3 1 2 4 3 1 1 4 2 2 3 4 1 3 2 4 2 4 1 3 3 2 4 1 1 3 2 4 2 4 1 3 1 4 3 2 4 2 1 4 1 3 3 2 3 2 1 1 4 1 3 4 2 3 2 1 3

1 3 4 1 2 4 2 1 2 4 1 3 3 4 1 3 2 4 1 3 2 4 1 2 2 4 1 2 4 3 1 3 2 1 3 2 4 2 4 3 2 4 1 3 3 2 4 1 3 4 1 1 3 2 4 2 3 2 2 4 1 3 4 1 3

1 3 4 1 3 4 1 2 4
2 1 3 2 1 3 4 1 3
3 4 1 3 2 1 3 2 4
1 3 2 4 3 2 4 1 2
2 4 1 2 4 1 3 4 3

Each of the 5×4, 5×6, 5×7, and 5×9 grids begins with the column 1 2 3 1 2 and the set {4, 6, 7, 9} is a complete residue system (mod 4). To color a 5 × n grid for n ≠ 5, select the value of 4, 6, 7, 9 that n is congruent to (mod 4), say a, and adjoin (n − a)/4 copies of the 5 × 4 grid to the 5 × a grid. This will be a proper coloring.

Note that except for the 5 × 5 grid, the first horizontal cycle C_{h}(1) of each grid formed this way has the distinct triple property.

Corollary 3.5. If G is a 6-regular right-diagonal m × n grid on the torus with m, n ≥ 3, then there is a 4-coloring of G with the first horizontal cycle C_{h}(1) and the first vertical cycle C_{v}(1) having distinct triples unless m or n = 5. If m = 5 (respectively, n = 5), there is a 4-coloring with the first horizontal (resp., vertical) cycle having distinct triples unless m = n = 5.

Proof. It is routine to check that the distinct triple property holds in all cases of the colorings in the proofs of Lemmas 3.1, 3.2, 3.4 and Theorem 3.3.

Notice that no 3-color theorem is possible in this setting since a m×n grid is 3-colorable if and only if 3 divides both m and n. The m × 3 grids have edge-width three, and even if the edge-width is increased to 4, such a 3-color theorem is not possible since one can check that the 4 × n grids are never 3-colorable.

Theorem 3.6. Let G be a 6-regular right-diagonal (m × n; i) grid on the torus for some i, 1 < i ≤ m. Then if 3 ≤ m, n, G can be 4-colored except possibly in the case when m = 5, or when i = 2 and n = m or m + 1, or when i = 3 and n = m.

Proof. We color using rotations as before except that we require extra columns due to the presence of the i-shift. If m, y ≥ 3 (where y will be specified later) and m ≠ 5, we color the (unshifted) m × y grid as in Theorem 3.3. Then in G we use this coloring on C_{v}(j), j = 1, 2, ..., y+1 with the coloring on C_{v}(y + 1) identical to that on C_{v}(1). Note that by Corollary 3.5 the coloring on C_{v}(y+1) has the distinct triples property. (If y < m, then this cycle is a horizontal cycle in the y ×m grid.) Then we use the remaining columns of G to make a transition from the coloring ϕ on C_{v}(y + 1) to the coloring on C_{v}(1), shifted to have the ith vertex at the top. We do this by using ϕ_{−1}, applying it successively m − i + 1 times on the columns C_{v}(y + 2), ..., C_{v}(y + m − i + 2). At this point the coloring on the final column is identical to that on C_{v}(1) except that the coloring is rotated to match that of C_{v}(1) shifted to have its ith vertex on top. Thus we have a valid coloring of the (m × n; i) grid with n = y + m − i + 1 provided that y ≥ 3. The inequality y ≥ 3 fails only when i = 2 and n = m or m + 1, or when i = 3 and n = m.

Theorem 3.7. Let G be a 6-regular right-diagonal (m × n; i) grid on the torus with 3 ≤ m, n. Then G can be 4-colored except in the cases of a (3 × 3; 2), or (3 × 3; 3) grid; a (5 × 3; 2), or (5 × 3; 3) grid; and a (5 × 5; 3), or (5 × 5; 4) grid.

Proof. Suppose m ≠ 5 and i = 2 and n = m, or i = 2 and n = m + 1, or i = 3 and n = m. We will show that G can be 4-colored. Together with Theorem 3.6 this proves the result in the cases where m ≠ 5. To account for the i shift, we now use the coloring rotation ϕ_{2}. As in the proof of Theorem 3.6, color the m × y grid and use this coloring in G on C_{v}(j), j = 1, 2, ..., y + 1 with the coloring on C_{v}(y + 1) identical to that on C_{v}(1). Call the latter coloring ϕ.

Then if i = 3 we apply ϕ_{2} to obtain a coloring on C_{v}(y + 2) which is identical to that on C_{v}(1) but with the third vertex shifted to the top. Thus we have a proper coloring of the (m × n; 3) grid with n = y + 1 which is valid provided n − 1 ≥ 3. The only impossible case is when G is a (3 × 3; 3) grid.

If i = 2, we apply ϕ_{2} to obtain a coloring on C_{v}(y+2) and then apply ϕ_{−1} to obtain a coloring of C_{v}(y +3) which is identical to that on C_{v}(1) but with the second vertex shifted to the top. Thus we have a proper coloring of the (m × n; 2) grid with n = y + 2 which is valid provided n − 2 ≥ 3. The only impossible cases are when G is a (3 × 3; 2) grid; a (3 × 4; 2) grid; or a (4 × 4; 2) grid. The third case can be 4-colored by alternately 2-coloring the vertical cycles. The second case can be 4-colored by

1 3 4 3
2 1 2 4
3 4 1 2

It is straightforward to check that the size of the largest independent set in a (3 × 3; 2) or a (3 × 3; 3) grid is 2, and hence that neither of these can be 4-colored.

Now suppose m = 5 so that we cannot rotate a coloring on vertical cycles. First we show that (5 × n; 2) grids are 4-colorable for n ≥ 5. Note that, up to color permutation and rotation, there are two 4colorings of the 5-cycle: 1, 2, 3, 1, 2 and 1, 2, 3, 4, 2. Then the (5 × 2; 2) grid is 4-colorable by starting with either of the following or a rotation of them:

1 3 2 4 3 2 1 3 2 4 1 3 2 1 3 2 4 1 2 4

Thus a (5×n; 2) grid can be 4-colored, by first coloring the (unshifted) 5 × (n − 2) grid and then regardless of the coloring of C_{v}(1), adding on the desired remaining two columns. This is valid provided n ≥ 5.

Similarly a (5 × 4; 3) grid is 4-colorable with either

1 3 2 1 2 4 3 4 3 2 1 3 1 3 2 4 2 4 1 3 1 3 2 1 2 1 3 2 3 2 4 3 4 1 2 4 2 4 1 3

so that a (5×n; 3) grid can be 4-colored, by first coloring the (unshifted) 5 × (n − 4) grid and then adding on the necessary remaining four columns. This is valid provided n ≥ 7.

Similarly the (5 × 4; 4) grid can be 4-colored with both starting 4colorings so that a (5 × n; 4) grid can be 4-colored for n ≥ 7.

1 4 3 2 2 1 4 3 3 2 1 4 1 4 2 3 2 3 1 4 1 3 2 1 2 1 4 3 3 2 1 4 4 3 2 3 2 4 1 4

However, the (5×4; 5) grid can be 4-colored with the starting column 1, 2, 3, 4, 2, but not the starting column 1, 2, 3, 1, 2. We can find a 4coloring of the (5×5; 5) grid with starting column 1, 2, 3, 1, 2, see below. This proves that the (5 × n; 5) grid can be 4-colored provided n ≥ 8.

1 3 2 1 4 2 1 3 2 3 3 2 4 1 4 1 3 2 3 1 2 4 1 4 2 1 3 4 1 2 1 3 4 3 2 1 3 4 3 2 4 2 4 1 2

It is straightforward to check that the size of the largest independent set in the (5 × 3; 2) or (5 × 3; 3) is 3; and that the size of the largest independent set in a (5 × 5; 3) or (5 × 5; 4) is less than 7, so that these grids cannot be 4-colored. We 4-color the remaining small grids not covered by our general results in an appendix at the end of the paper.

Theorem 3.8. Let G be a 6-regular right-diagonal (m × 2; i) grid on the torus with 1 ≤ i ≤ m. Then if m is even, G can be 4-colored. If i = 1 and m is odd, G cannot be 4-colored. If i > 1 and m is odd, then G is also a (r × s; t) grid where r, s ≠ 2, rs = 2m, and 1 ≤ t ≤ r, and so its colorability is settled by other results.

Proof. As mentioned previously an unshifted m × 2 grid is 4-colorable if and only if m is even. The same coloring works for a (m × 2; i) grid when m is even, namely by assigning two colors alternately to each of the vertical cycles.

Suppose i > 1 and m is odd. Let the vertices of C_{v}(1) be labelled 1, 2, ..., m, and those of C_{v}(2) by 1′, 2′, ..., m′. As explained after Altshuler’s Theorem, G can be redrawn as another grid graph by following the cycle 1, 1′, i, i′, 2i − 1, (2i − 1)′, ... until ki − k ≡ 0 (mod m). Let r = gcd(i − 1, m). If r = 1, then G is represented as a (2m × 1; j) grid for some j, 1 < j ≤ 2m, and we refer to Theorem 3.9. Otherwise since r is odd, it is at least 3, and G is represented as an (r × (2k); j) grid with r, 2k > 2 and so is covered by Theorem 3.3, 3.6 or 3.7.

We are left with the (m × 1; i) grid cases; these are circulant graphs with vertex j adjacent (clockwise) to j−1, j+i−2, j+i−1, j+1, j−i+2, and j −i+1 (mod m) for j = 1, 2, ..., m, or equivalently with difference set {1, i − 2, i − 1}. The grids with i = 1 and 2 contain loops and so we do not consider them. The grids with i = 3 contain multiple edges and are circulants with vertex j adjacent to vertices j − 2, j − 1, j + 1, and j +2 (mod m). These can be 4-colored for m > 5 by abc … abc if m ≡ 0 (mod 3), abc … abcabcd if m ≡ 1 (mod 3), and by abc … abcadcbd if m ≡ 2 (mod 3). In the grids with i = 4 every successive set of 4 vertices forms a complete graph so these graphs can be 4-colored if and only if 4 divides m. If 4 does not divide m and m ≥ 15, it is easy to check that the grid is 5-colorable. These grids are the family of 5-chromatic, 6-regular toroidal graphs of edge-width three referred to in Section 1; the cycle (1, 2, 3) is non-contractible. The remaining cases of 5 ≤ i ≤ m are more complex; due to symmetry we may assume that i ≤ ⌈m/2⌉.

Theorem 3.9. Consider 6-regular right-diagonal (m × 1; i) grids on the torus with 5 ≤ i ≤ ⌈m/2⌉. Then for each value of i there is a finite number of these grids that are not 4-colorable.

For example, direct computation shows that the (m × 1; 5) grids are 4-colorable for m ≥ 26, and are not 4-colorable only for m = 10, 11, 13, 17, 18 and 25. Similarly the (m×1; 6) grids are all 4-colorable for m ≥ 18.

Proof. Let the vertices be labelled 0, 1, …, m − 1 so that vertex 0 is adjacent to vertices m−1, i−2, i−1, 1, m−i+2, and m−i+1. Suppose that i is odd with i = 2k + 1 for some integer k. For m = 4k − 1 we color the vertices by (ab)^{k}(cd)^{k−1}c; that is, by k repetitions of ab, then k − 1 repetitions of cd, followed by one c. For m = 4k we color with (ab)^{k}(cd)^{k}.

To check that this is a valid coloring, in this and subsequent cases, we list the vertex numbers in each color class and then check that no two numbers in one class differ by an element of the difference set S = {1, 2k − 1, 2k} with all work performed (mod m). In these cases we have, respectively:

a : 0  2 … 2k − 4 2k − 2
b : 1 3 … 2k − 3 2k − 1
c : 2k 2k + 2 … 4k − 4 4k − 2
d : 2k + 1 2k + 3 … 4k − 3

\begin{matrix}a : & 0 & 2 & … & 2k − 4 & 2k − 2 \\ b : & 1 & 3 & … & 2k − 3 & 2k − 1 \\ c : & 2k & 2k + 2 & … & 4k − 4 & 4k − 2 \\ d : & 2k + 1 & 2k + 3 & … & 4k − 3 & 4k − 1 \end{matrix}

Note that these two colorings are “compatible,” meaning that concatenating one with the other gives a valid coloring. For example, with m = 4k − 1 + 4k = 8k − 1, a valid coloring is given by

(ab)^{k}(cd)^{k−1}c(ab)^{k}(cd)^{k}

More generally, if m = A(4k −1)+B(4k) with A and B nonnegative integers, then we can color the (m×1; 2k+1) grid with first the coloring for 4k − 1 vertices, (ab)^{k}(cd)^{k−1}c, concatenated A times, and followed with B copies of the second coloring, (ab)^{k}(cd)^{k}. This gives a proper coloring of all m vertices. Since 4k − 1 and 4k are relatively prime, all m sufficiently large can be expressed as A(4k − 1) + B(4k). In fact, if x and y are relatively prime integers, then each n ≥ (x − 1)(y − 1) can be expressed as n = Ax + By for some nonnegative integers A and B ([23], see also [17]); thus we can 4-color all such graphs with m ≥ (4k − 2)(4k − 1) = (2i − 4)(2i − 3).

Next let i be even so that i = 2k + 2 and vertex 0 is adjacent to 1, 2k, 2k + 1, m − 1, m − 2k, and m − 2k − 1 for some integer k with i = 2k + 2; now we have the difference set S = {1, 2k, 2k + 1}. We solve this in three cases, modulo 6.

First suppose that i ≡ 0 (mod 6), so 2k = 6j − 2 and that S = {1, 6j − 2, 6j − 1} (so 3j − 1 = k). For every m divisible by 3, (abc)^{(m/3)} is a valid coloring. For m = 24j − 8, we use the coloring (abc)^{2j}(dbc)^{(2j−1)}(dac)^{(2j−1)}(dab)^{(2j−1)}d. It is straightforward to check that these are correct colorings. Note that the colorings are compatible (can be concatenated) since the first coloring is the start of the second; even better, for any m divisible by 3, the latter coloring is compatible with (abc)^{(m/3)}. Since 3 and 24j − 8 are relatively prime, these circulants on m ≥ 2(24j − 9) = 2(8k − 1) = 16k − 2 = 8i − 18 vertices can all be 4-colored.

Next suppose that i ≡ 2 (mod 6), so 6j = 2k and S = {1, 6j, 6j +1}. For m = 6j + 2 we color with (abc)^{j}(adc)^{j}bd. For m = 12j + 1 we color with

(abc)^{j}(adc)^{j}bd(abc)^{(j−1)}(adc)^{j}bd

The latter coloring is compatible with the former, seen by the initial segment. Since gcd(6j + 2, 12j + 1) = 1, for m ≥ 12j(6j + 1) = 4k(2k + 1) = 2(i − 2)(i − 1) all these graphs can be 4-colored.

And finally, let i ≡ 4 (mod 6), so 6j + 2 = 2k and S = {1, 6j + 2, 6j + 3}. (Every coloring of the form (abc)^{s}d(abc)^{t}d is valid when s, t lie in {2k, 2k + 1}, but we don’t need that much.) For m = 6j + 4 we can color with (abc)^{(2j+1)}d, and for m = 12j + 5 we color with (abc)^{(2j+1)}d(abc)^{2j}d. These colorings are compatible since one is the start of the other. And gcd(6j + 4, 12j + 5) = 1 so that for all m ≥ (6j + 3)(12j + 4) = 4k(2k + 1) = 2(i − 2)(i − 1) we can 4-color this form of circulant graph.

Although we would like to, we cannot at present give a bound on edge-width for the (m×1; i) grids that implies 4-colorability. Note that in these graphs the (i − 1)-cycle (0, 1, 2, ..., i − 2, 0) is embedded as a noncontractible cycle, as are the cycles

(0, i − 1, 2i − 2, …, qi − q, qi − q + 1, qi − q + 2, …, m − 1, 0)

(0, i − 1, 2i − 2, …, qi − q, (q + 1)(i − 1), (q + 1)(i − 1) − 1, (q + 1)(i − 1) − 2, …, 1, 0)

where q = ⌊\frac{m}{i−1}⌋ and numbers are read modulo m. Either q(i − 1) or (q + 1)(i − 1) is within (i − 1)/2 of m. Thus the edge-width of the (m × 1; i) grid is at most min\{i − 1, \frac{m}{i−1} + \frac{i−1}{2}\}.

Theorem 3.9 gives a lower bound B_{i} on m, such that if m ≥ B_{i}, then the (m × 1; i) grid can be 4-colored. We have run computer searches for i = 5, 6, 7, 8, 9, 10 to establish the actual least value M_{i} such that every (m × 1; i) grid with m ≥ M_{i} can be 4-colored, and present these bounds below. The last column in the table is the largest edge-width in a non-4-colorable shift i grid.

i M_{i} B_{i} edge-width
5 26 42  4
6 18 30  4
7 18 110  3
8 34 84  5
9 27 210  5
10 27 144  3

Figure 3. Actual and estimated bounds on m for which an (m × 1; i) grid is 4-colorable.

Additional results on coloring these and other circulants can be found in [6].

Acknowledgements: We would like to thank the following people for helping us with this work: M. O. Albertson, L. Carter, D. Fisher, S. Fisk, M. Hovey, L. Krompart, and C. Thomassen. We would also like to thank the referees for helpful corrections and comments.

References

[1] M. O. Albertson and J. P. Hutchinson, Hadwiger’s conjecture and sixchromatic toroidal graphs, Graph Theory and Related Topics (J.A. Bondy and U.S.R. Murty, eds.) Academic Press, New York 1979.

[2] M. O. Albertson and J. P. Hutchinson, On six-chromatic toroidal graphs, Proc. London Math. Soc. 41 (1980) 533-556.

[3] M. O. Albertson and W. Stromquist, Locally planar toroidal graphs are 5colorable, Proc. Amer. Math. Soc. 84 (1982) 449–456.

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

[5] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976) 711–712.

[6] K. L. Collins, D. Fisher, J. P. Hutchinson, On 3- and 4-coloring some circulant graphs, in preparation.

[7] S. Fisk, The nonexistence of colorings, J. Combin. Theory, Ser. B, 24 (1978) 247–248.

[8] M. R. Garey and D. S. Johnson, Computers and Intractibility, W.H. Freeman, San Francisco, 1979.

[9] N. Hartsfield and G. Ringel, Minimal quadrangulations of orientable surfaces, J. Combin. Theory Ser. B 46 (1989) 84–95.

[10] P. J. Heawood, Map-colour theorem, Quart. J. Pure Appl. Math. 24 (1890) 332–338.

[11] P. J. Heawood, On the four-colour map theorem, Quart. J. Pure Appl. Math. 29 (1898) 270–285.

[12] J. P. Hutchinson, On coloring maps made from Eulerian graphs, in “Proceedings 5th British Combinatorial Conf.,” Congr. Numer. 15 (1975) 343–354.

[13] J. P. Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided, J. Combin. Theory Ser. B 65 (1995) 139–155.

[14] J. P. Hutchinson and B. Richter, personal communication.

[15] T. R. Jensen and B. Toft, Graph Coloring Problems, John Wiley & Sons, New York, 1995.

[16] A. B. Kempe, On the geographical problem of the four colours, Amer. J. Math. 2 (1879) 193–200.

[17] A. Nijenhuis and H. S. Wilf, Representations of integers by linear forms in nonnegative integers, J. Number Theory, 4 (1972) 98–106.

[18] G. Ringel, “Map Color Theorem,” Springer-Verlag, Berlin, 1974.

[19] G. Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968) 438–445.

[20] N. Robertson, D. Sanders, P. Seymour, and R. Thomas, The four colour theorem, J. Combin. Theory Ser. B, 70 (1997) 2-44.

[21] R. Steinberg, The state of the three color problem, Quo Vadis, Graph Theory? (J. Gimbel, J. W. Kennedy, and L. V. Quintas, eds.), Ann. Discrete Math., 55 (1993) 211–248.

[22] R. Steinberg, An update on the state of the three color problem, Graph Theory Notes of New York XXV (J.W. Kennedy and L.V. Quintas, eds.) New York Academy of Sciences, 1993.

[23] J. Sylvester, Mathematical Questions, with their solutions, Educational Times, 41 (1884) 21.

[24] C. Thomassen, Embeddings of graphs with no short noncontractible cycles, J. Combin. Theory Ser. B 48 (1990) 155–177.

[25] C. Thomassen, Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface, Trans. Amer. Math. Soc. 323 (1991) 605–635.

[26] C. Thomassen, Five-colorings maps on surfaces, J. Combin. Theory Ser. B 59 (1993) 89–105.

[27] C. Thomassen, Trees in triangulations, J. Combin. Theory Ser. B 60 (1994) 56–62.

[28] C. Thomassen, Five-coloring graphs on the torus, J. Combin. Theory Ser. B 62 (1994) 11–33.

[29] D. B. West, Introduction to Graph Theory, Prentice Hall, 1996.

[30] D. A. Youngs, 4-chromatic projective graphs, J. Graph Theory 21 (1996) 219–227.

COLORING APPENDIX

We color the (5 × 4; 2) grid.

1 4 2 3
2 1 4 1
3 2 3 2
4 1 4 3
2 3 1 4

We color the (5 × 6; 3) grid.

1 4 2 3 1 4
2 1 4 2 3 1
3 2 3 1 2 3
4 1 2 3 1 4
2 3 1 4 2 3

We color the (5 × 3; 4) and the (5 × 6; 4) grids.

1 3 2 2 1 3 3 2 4 4 1 3 2 4 1 1 3 2 1 3 2 2 1 3 2 4 3 3 2 4 1 2 4 4 1 3 4 1 3 2 4 1 3 4 1

We color the (5 × 3; 5), (5 × 6; 5), and the (5 × 7; 5) grid.

1 4 3 2 1 4 3 2 3 4 1 4 2 3 1 1 4 2 1 4 3 2 1 4 2 1 4 3 2 3 4 2 3 4 1 2 3 1 4 2 3 1 4 2 1 1 3 2 4 3 1 4 2 1 3 2 4 2 3 3 2 4 1 3 1 4 1 3 2 4 2 3 1 2 4 1 3 1 4 2

Dept. of Mathematics, Wesleyan University, Middletown CT 06459

E-mail address: kcollins@wesleyan.edu

Dept. of Mathematics and Computer Science, Macalester College, St. Paul MN 55105

E-mail address: hutchinson@macalester.edu