# Chromatic numbers of Cayley graphs of abelian groups: Cases of small
dimension and rank

Jonathan Cervantes  University of California, Riverside, Dept. of Mathematics,
Skye Hall, 900 University Ave., Riverside, CA 92521<EMAIL_ADDRESS>Mike
Krebs  California State University, Los Angeles, Dept. of Mathematics, 5151
State University Drive, Los Angeles, CA 91711<EMAIL_ADDRESS>
###### Abstract

A connected Cayley graph on an abelian group with a finite generating set $S$
can be represented by its Heuberger matrix, i.e., an integer matrix whose
columns generate the group of relations between members of $S$. In a companion
article, the authors lay the foundation for the use of Heuberger matrices to
study chromatic numbers of abelian Cayley graphs. We call the number of rows
in the Heuberger matrix the dimension, and the number of columns the rank. In
this paper, we give precise numerical conditions that completely determine the
chromatic number in all cases with dimension $1$; with rank $1$; and with
dimension $\leq 3$ and rank $\leq 2$. For such a graph without loops, we show
that it is $4$-colorable if and only if it does not contain a $5$-clique, and
it is $3$-colorable if and only if it contains neither a diamond lanyard nor a
$C_{13}(1,5)$, both of which we define herein. In a separate companion
article, we show that we recover Zhu’s theorem on the chromatic number of
$6$-valent integer distance graphs as a special case of our theorem for
dimension $3$ and rank $2$.

Keywords— graph, chromatic number, abelian group, Cayley graph, circulant
graph

##  1 Introduction

Given an $m\times r$ integer matrix $M$, let $H$ be the set of all linear
combinations of the columns of $M$ with integer coefficients. Let $\mathbb{Z}$
denote the group of integers under addition, and let $\mathbb{Z}^{m}$ denote
the $m$-fold direct product of $\mathbb{Z}$ with itself. Let
$e_{j}\in\mathbb{Z}^{m}$ denote the $m$-tuple (regarded as a column vector)
whose $i$th component is $1$ if $i=j$ and is $0$ otherwise. Let $S=\\{H\pm
e_{1},\dots,H\pm e_{m}\\}$. We may then form the Cayley graph whose underlying
group is $\mathbb{Z}^{m}/H$ with respect to the generating set $S$. We denote
by $M^{\text{SACG}}_{X}$ the graph formed in this manner. We call
$M^{\text{SACG}}_{X}$ a standardized abelian Cayley graph, and we call $M$ an
associated Heuberger matrix. As discussed in [1], the study of chromatic
numbers of Cayley graphs on abelian groups can be reduced to the study of
standardized abelian Cayley graphs and their Heuberger matrices. Many, many
particular cases of chromatic numbers of Cayley graphs on abelian groups have
been studied; see the introduction to [1] for a long list of examples.

Our main results (Theorems 2.9 and 2.14) give precise and easily checked
numerical conditions that completely determine the chromatic number when the
associated Heuberger matrix is $2\times 2$ or $3\times 2$. These results can
be summarized as follows: Suppose such a graph does not have loops. Then it is
$4$-colorable if and only if it does not contain a $5$-clique, and it is
$3$-colorable if and only if it contains neither a diamond lanyard (see Def.
2.2) nor a $\text{Cay}(\mathbb{Z}_{13},\\{\pm 1,\pm 5\\})$.

Whether such subgraphs occur, we show, can be ascertained quickly from the
entries of the Heuberger matrix. After excluding some trivial exceptional
cases, one first puts the matrix into a certain standardized form (lower
triangular form with positive diagonal entries for $2\times 2$ matrices,
“modified Hermite normal form” for $3\times 2$ matrices) without changing the
associated graph. Theorems 2.9 and 2.14 then provide formulas for the
chromatic number of graphs with matrices in this form.

We briefly sketch the method of proof. For $2\times 2$ matrices, the main
result (Thm. 2.9) follows quickly by combining Heuberger’s theorem on
chromatic numbers of circulant graphs with the methods of [1]. The principal
result for $3\times 2$ matrices (Thm. 2.14) requires more work. The main idea
is to apply the graph homomorphisms of [1] to obtain upper bounds on the
chromatic number, utilizing the previous results from the $2\times 2$ case.

In [8], Zhu finds the chromatic number for an arbitrary integer distance graph
of the form $\text{Cay}(\mathbb{Z},\\{\pm a,\pm b,\pm c\\})$, where $a,b,$ and
$c$ are distinct positive integers. Such graphs, as shown in [1], have
associated $3\times 2$ matrices. In another companion paper [2], we
demonstrate how Thm. 2.14 yields Zhu’s theorem as a corollary of our main
theorem about $3\times 2$ Heuberger matrices.

One obvious future direction for this work will be to investigate what happens
when the matrices are larger. For example, the case of a graph $X$ with an
associated $m\times 2$ Heuberger matrix when $m\geq 4$ seems well within reach
using methods developed in this paper, and we plan to tackle that next.

As we show in the proofs of our main theorems, when an abelian Cayley graph
$X$ has an associated $2\times 2$ or $3\times 2$ Heuberger matrix, an optimal
coloring for $X$ can always be realized as a pullback, via a graph
homomorphism, of a coloring of a circulant graph. We pose the question (akin
to that asked in [5]): Is that statement true for all connected, finite-degree
abelian Cayley graphs?

Moreover, we propose the following conjecture: Let $X$ be a standardized
abeliam Cayley graph with an associated Heuberger matrix $M_{X}$. If $X$ does
not have loops, and the determinant of every $2\times 2$ minor of $M_{X}$ is
divisible by $3$, then $X$ is $3$-colorable.

This article depends heavily on [1], which we will refer to frequently. The
reader should assume that all notation, terminology, and theorems used but not
explained here are explained there.

##  2 Main theorems

In [1], we laid the groundwork for our main techniques, and we employed them
to prove the Tomato Cage Theorem, which completely determines the chromatic
number in the case where $H$ has rank $1$. In this section, we turn our
attention to our main results, which concern the case where $H$ has rank $2$.
Let $X$ be a standardized abelian Cayley graph, and let $m$ be the number of
rows in an associated Heuberger matrix $M_{X}$.

In Subsection 2.1, we quickly dispense with the case where $m=1$.

For $m=2$, we first apply isomorphisms to $X$ as in [1] to put the matrix in a
standard form without changing the associated graph. We then clear aside the
somewhat aberrant situations where $X$ is bipartite, $X$ has loops, or the
matrix has a zero row. Excluding these possibilities, we show that if the
matrix entries are not relatively prime, then $\chi(X)=3$; otherwise, $X$ is
isomorphic to a circulant graph, and its chromatic number is given by a
theorem of Heuberger’s. Subsection 2.3 contains the precise statements and
proofs.

For $m=3$, we again begin by putting the matrix into a standard form we call
“modified Hermite normal form,” as detailed in Subsection 2.4. Again the
“aberrant” situations can be handled quickly. We then determine the chromatic
number in the remaining cases. To do so, we subtract rows to produce a
homomorphism to a graph with an associated $2\times 2$ matrix, for which we
already have a complete theorem. When this fails to produce a $3$-coloring, we
modify the mapping. We show that whenever we are unable in this manner to
properly $3$-color $X$, it must be that in fact $X$ is not properly
$3$-colorable, and our procedure instead yields a $4$-coloring of $X$. These
unusual cases, we show, fall into one of six families, and we state precise
numerical conditions for when they occur. Subsection 2.5 contains the precise
statements and proofs.

As a by-product of our proofs, we show that for the class of graphs we
consider, if they don’t have loops, then $K_{5}$ (the complete graph on $5$
vertices) is the only obstacle to $4$-colorability, and “diamond lanyards” and
“$C_{13}(1,5)$” (both of which we define in Subsection 2.2) are the only
obstacles to $3$-colorability.

In Subsection 2.6, we furnish a synopsis of the procedures involved — an
algorithm to determine the chromatic number whenever the Heuberger matrix is
of size $m\times 1,1\times r,2\times r$, or $3\times 2$.

###  2.1 The case $m=1$

The case $m=1$ can be dealt with immediately.

######  Lemma 2.1.

Suppose $X$ is a standardized abelian Cayley graph defined by
$(y_{1}\;\cdots\;y_{r})^{\text{SACG}}_{X}$ for some integers
$y_{1}\,\dots,y_{r}$, not all $0$. Let $e=\gcd(y_{1}\,\dots,y_{r})$. Then $X$
has loops (and therefore is not properly colorable) if and only if $e=1$;
otherwise, we have that $\chi(X)=2$ if $e$ is even, and $\chi(X)=3$ if $e$ is
odd.

###### Proof.

Applying column operations as in [1, Lemma LABEL:general-lemma-isomorphisms],
we can in effect perform the Euclidean algorithm so as to acquire an
isomorphic standardized abelian Cayley graph
$(e\;0\;\cdots\;0)^{\text{SACG}}_{X^{\prime}}=(e)^{\text{SACG}}_{X^{\prime}}$.
The result follows from [1, Example LABEL:general-example-cycle]. ∎

If $y_{1}=\cdots=y_{r}=0$, then $\chi(X)=2$, by [1, Lemma LABEL:general-lemma-
bipartite].

###  2.2 Diamond lanyards and $C_{13}(1,5)$

Recall that a _diamond_ is a graph with $4$ vertices, exactly one pair of
which consists of nonadjacent vertices. In other words, a diamond is a $K_{4}$
(complete graph on $4$ vertices) with one edge deleted. The two vertices not
adjacent to one another are the _endpoints_ of the diamond.

######  Definition 2.2.

An _unclasped diamond lanyard of length_ $1$ is a diamond. Recursively, we
define an _unclasped diamond lanyard $U$ of length $\ell+1$_ to be the union
of an unclasped diamond lanyard $Y$ of length $\ell$ and a diamond $D$, such
that $Y$ and $D$ have exactly one endpoint in common. The _endpoints_ of $U$
are the endpoint of $Y$ which is not an endpoint of $D$, and the endpoint of
$D$ which is not an endpoint of $Y$. A _(clasped) diamond lanyard of length_
$\ell$ is obtained by adding to an unclasped diamond lanyard $U$ of length
$\ell$ an edge between the endpoints of $U$. We call that edge a _clasp_.

Def. 2.2 does not preclude the possibiity of the diamonds in the lanyard
having edges in common. For example, Let $X=\text{Cay}(\mathbb{Z}_{5},\\{\pm
1,\pm 2\\})$. Then $X$ is a $K_{5}$ graph with vertex set $\\{0,1,2,3,4\\}$.
We write an edge in $X$ as a string of two vertices. So $X$ contains as a
subgraph a diamond with edges $01,02,12,13,23$ and endpoints $0$ and $3$. It
also contains as a subgraph a diamond with edges $41,42,12,13,23$ and
endpoints $4$ and $3$. The edge sets of these two diamonds are non-disjoint.
Taking the union of these two diamonds produces an unclasped diamond lanyard
of length two with endpoints $0$ and $4$. Observing that $04$ is also an edge
in $X$, indeed $X$ contains a clasped diamond lanyard as a subgraph.

We sometimes refer to a clapsed diamond lanyard simply as a _diamond lanyard_.
A diamond lanyard of length $1$ is a $K_{4}$, and a diamond lanyard of length
$2$ where the two diamonds have disjoint edges is called a _Mosers’ spindle_
[7]. Figure 1 illustrates a diamond lanyard of length $4$.

Figure 1: A diamond lanyard of length $4$

(We would have preferred to have dubbed these “diamond chain necklaces,” but
the term “necklace graph” already has a standard meaning.)

We observe that diamond lanyards are not $3$-colorable. For suppose we have a
proper $3$-coloring. Note that in any proper $3$-coloring of a diamond, its
endpoints must have the same color. Hence the endpoints of the diamond lanyard
must have the same color, but they are adjacent, which is a contradiction.
Thus, we have the following lemma.

######  Lemma 2.3.

Suppose $X$ is a graph containing a diamond lanyard as a subgraph. Then
$\chi(X)\geq 4$.

We remark that a diamond lanyard of length $\geq 2$, where the defining
diamonds have mutually disjoint edge sets, is a unit-distance graph; hence the
chromatic number of the plane is at least $4$. (Indeed, as discussed in the
introduction of [1], it is now known to be at least $5$.)

We now turn our attention to the other object that can stand in the way of
$3$-colorability for our graphs. Let $C_{13}(1,5)$ be the circulant graph
$\text{Cay}(\mathbb{Z}_{13},\\{\pm 1,\pm 5\\})$. (For more about this
notation, see Def. 2.5.) Heuberger proves the following lemma in [4] using a
“vertex-chasing” argument. Here we prove it by showing that the independence
number is $4$. We include this proof so that it might suggest generalizations.

######  Lemma 2.4.

The chromatic number of $C_{13}(1,5)$ is $4$.

###### Proof.

It is straightforward to find a proper $4$-coloring of $C_{13}(1,5)$. We now
let $A$ be an independent set of vertices in $C_{13}(1,5)$. We will show that
$|A|\leq 4$. This will prove the lemma.

Suppose that $|A|\geq 5$; we will show that this leads to a contradiction.
First observe that we must have $|A|\leq 6$. For if $|A|\geq 7$, then $A$
would contain the adjacent vertices $x$ and $x+1$ for some
$x\in\mathbb{Z}_{13}$. Because $|A|\leq 6<\frac{13}{2}$, there must be
$x\in\mathbb{Z}_{13}$ such that $x\notin A$ and $x+1\notin A$. From $|A|\geq
5$ we find that

$\\{x+2,x+3,x+4,x+5,x+6,x+7\\}\cap A\text{ or
}\\{x+8,x+9,x+10,x+11,x+12\\}\cap A$

must contain at least $3$ elements. Because $z$ and $z+1$ are adjacent for all
$z\in\mathbb{Z}_{13}$, these three elements must be $x+y-2,x+y,$ and $x+y+2$
for some $y\in\\{4,5,10\\}$. Using the fact that $a\pm 1\notin A$ and $a\pm
5\notin A$ whenever $a\in A$, we see that

$x+y+1,x+y+3,x+y+5,x+y+6,x+y+7,x+y+8,x+y+10,x+y+12\notin A.$

Because $|A|\geq 5$, we know that $A$ must contain at least two elements other
than $x+y-2,x+y,$ and $x+y+2$, but the only remaining elements in
$\mathbb{Z}_{13}$ are $x+y+4$ and $x+y+9$. However, $x+y+4$ and $x+y+9$ are
adjacent and so cannot both be in $A$.∎

###  2.3 The case $m=2$

In this subsection, we completely determine $\chi(X)$ when $X$ has a $2\times
2$ matrix as an associated Heuberger matrix. (Note that if the number of
columns exceeds the number of rows, we can perform column operations as in [1,
Lemma LABEL:general-lemma-isomorphisms] to get a zero column, and then delete
it. So the results of this section, together with the Tomato Cage Theorem,
completely take care of all dimension $2$ cases.)

Suppose $X$ is a standardized abelian Cayley graph with a $2\times 2$
Heuberger matrix. By performing row and column operations as in Lemma [1,
Lemma LABEL:general-lemma-isomorphisms], one can show that $X$ is isomorphic
to a standardized abelian Cayley graph $X^{\prime}$ with an associated matrix
$M_{X^{\prime}}$ that is lower-triangular, and such that the diagonal entries
of $M_{X^{\prime}}$ are non-negative. Hence we may restrict our attention to
the case where $M_{X}$ is a $2\times 2$ lower-triangular matrix with
nonnegative diagonal entries.

Next we delve into a class of graphs that play a crucial role in the main
theorem for this subsection.

######  Definition 2.5.

Let $a,b$, and $n$ be integers with $n\neq 0$ and $\gcd(a,b,n)=1$ and $n\nmid
a$ and $n\nmid b$. We say that $\text{Cay}(\mathbb{Z}_{n},\\{\pm a,\pm b\\})$
is a _Heuberger circulant_ , denoted $C_{n}(a,b)$. $\square$

The condition $\gcd(a,b,n)=1$ is equivalent to the connectedness of
$C_{n}(a,b)$, and the condition that $n\nmid a$ and $n\nmid b$ is equivalent
to the absence of loops.

In [4], Heuberger completely determines the chromatic number of all Heuberger
circulants, as follows.

######  Theorem 2.6 ([4, Theorem 3]).

Let $C_{n}(a,b)$ be a Heuberger circulant. Then

$\chi(C_{n}(a,b))=\begin{cases}2&\text{if }a\text{ and }b\text{ are both odd,
but }n\text{ is even}\\\ 5&\text{if }n=\pm 5\text{ and }a\equiv\pm
2b\;(\textup{mod}\;5)\\\ 4&\text{if }n=\pm 13,\text{ and }\;a\equiv\pm
5b\;(\textup{mod}\;13)\\\ 4&\text{if }(i)\;n\neq\pm 5,\text{ and }(ii)\;3\nmid
n,\text{ and }(iii)\;a\equiv\pm 2b\;(\textup{mod}\;n)\text{ or }b\equiv\pm
2a\;(\textup{mod}\;n)\\\ 3&\text{otherwise.}\end{cases}$

We note that [4] excludes the case $a\equiv\pm b\;(\textup{mod}\;n)$, in which
event $C_{n}(a,b)$ is an $n$-cycle. However, the theorem as stated here
includes this possibility as well.

Observe that the third case in Theorem 2.6 is precisely Lemma 2.4. Moreover,
for the fourth case, Lemma 2.3 shows that $\chi(C_{n}(a,b))\geq 4$, for the
following reason. First suppose that $a\equiv 2b\;(\textup{mod}\;n)$. Observe
that for all $x\in\mathbb{Z}_{n}$, there is a diamond in $C_{n}(a,b)$ with
vertex set $\\{x,x+a,x+2a,x+3a\\}$, where the endpoints are $x$ and $x+3a$.
Because $a\equiv 2b\;(\textup{mod}\;n)$ and $\gcd(a,b,n)=1$, we must have that
$\gcd(a,n)=1$. Moreover, because $3\nmid n$, we have that $\gcd(3a,n)=1$. Let
$m$ be a positive integer such that $3am\equiv 1\;(\textup{mod}\;n)$. Then
$C_{n}(a,b)$ contains a diamond lanyard with vertex set $\\{ja\;|\;0\leq j\leq
m\\}$, so by Lemma 2.3, we have that $\chi(C_{n}(a,b))\geq 4$. A similar
argument works when $a\equiv-2b\;(\textup{mod}\;n)$ or when $b\equiv\pm
2a\;(\textup{mod}\;n)$. This is essentially the reasoning in [4] for the lower
bounds in these cases. Hence a Heuberger circulant is $4$-colorable unless it
is $K_{5}$; and it is $3$-colorable unless it contains as a subgraph either a
diamond lanyard or it equals $C_{13}(1,5)$. (Recall that $K_{5}$ contains a
diamond lanyard, so we needn’t include it in the list of obstructions to
$3$-colorability.)

Next, we show that when the entries of the first column of $M_{X}$ are
relatively prime, then with some mild additional conditions imposed, $X$ is
isomorphic to a Heuberger circulant.

######  Lemma 2.7.

Let $X$ be a standardized abelian Cayley graph with associated Heuberger
matrix

$M_{X}=\begin{pmatrix}y_{11}&y_{12}\\\ y_{21}&y_{22}\end{pmatrix}.$

Suppose that $X$ does not have loops, that $\det(M_{X})\neq 0$, and that
$\gcd(y_{11},y_{21})=1$. Then $X$ is isomorphic to the Heuberger circulant
$C_{n}(a,b)$, where $a=-y_{21}$, $b=y_{11}$, and $n=\det(M_{X})$.

###### Proof.

Define a homomorphism $\varphi\colon\mathbb{Z}^{2}\to\mathbb{Z}_{n}$ by
$e_{1}\mapsto a,e_{2}\mapsto b$. Let $y_{1}$ and $y_{2}$ be the first and
second columns, respectively, of $M_{X}$. We must show that $\ker\varphi$
equals the $\mathbb{Z}$-span of $y_{1}$ and $y_{2}$. It is straightforward to
show that $\varphi(y_{1})=\varphi(y_{2})=0$, giving us one inclusion. We now
show the reverse inclusion. Suppose $\varphi((x_{1},x_{2})^{t})=0$. Then
$ax_{1}+bx_{2}\equiv 0\;(\textup{mod}\;n)$. Because $a$ and $b$ are relatively
prime, there exist integers $q,r$ such that $aq+br=1$. Using elementary number
theory as in [6], we find that $x_{1}=\ell nq+kb$ and $x_{2}=\ell nr-ka$ for
some integers $\ell,k$. Hence after some computations we find that

$\begin{pmatrix}x_{1}\\\ x_{2}\end{pmatrix}=ky_{1}+\ell n\begin{pmatrix}q\\\
r\end{pmatrix}=ky_{1}+\begin{pmatrix}\ell qy_{11}y_{21}-\ell qy_{21}y_{12}\\\
\ell ry_{11}y_{22}-\ell ry_{21}y_{12}\end{pmatrix}=(k+\ell qy_{22}-\ell
ry_{12})y_{1}+\ell y_{2}.\qed$

Note that after switching the columns of the matrix, Lemma 2.7 becomes a
special case of [1, Example LABEL:general-example-arbitrary-circulant-graph].
We have included it here separately so as to give a more elementary proof for
$2\times 2$ matrices.

We remark that not every graph with an associated $2\times 2$ Heuberger matrix
is isomorphic to a circulant. The graph $\begin{pmatrix}4&0\\\
2&4\end{pmatrix}_{X}^{\text{SACG}}$, for instance, provides a counterexample.
One computes that $X$ must have order $16$ and so, if circulant, would be of
the form $\text{Cay}(\mathbb{Z}_{16},S)$ for some $S$. Because $X$ is
connected and bipartite, and has degree $4$, we see that up to isomorphism, we
can assume $S=\\{\pm 1,\pm 3\\}$ or $S=\\{\pm 1,\pm 7\\}$. Direct arguments
(for example, counting the number of paths of length $2$ between various
vertices) show that neither choice of $S$ produces a circulant graph
isomorphic to $X$.

The following lemma characterizes $2\times 2$ matrices whose associated graphs
have loops. This occurs either when the determinant is nonzero and divides a
row, or else when one row is zero and the other has relatively prime entries.

######  Lemma 2.8.

Let $X$ be a standardized abelian Cayley graph with an associated matrix

$M_{X}=\begin{pmatrix}y_{11}&y_{12}\\\ y_{21}&y_{22}\end{pmatrix}$

Let $n=\det(M_{X})$. If $n\neq 0$, then $X$ has loops if and only if either
(i) $n\mid y_{11}$ and $n\mid y_{12}$ or (ii) $n\mid y_{21}$ and $n\mid
y_{22}$. If $n=0$, then $X$ has loops if and only if either (a)
$y_{11}=y_{12}=0$ and $\gcd(y_{21},y_{22})=1$, or (b) $y_{21}=y_{22}=0$ and
$\gcd(y_{11},y_{12})=1$.

###### Proof.

First suppose $n\neq 0$. We know that $X$ has loops if and only if $e_{1}$ or
$e_{2}$ is in the $\mathbb{Z}$-span $H$ of the columns of $M_{X}$. We have
$e_{1}\in H$ if and only if $M_{X}^{-1}e_{1}\in\mathbb{Z}^{2}$. But

$M_{X}^{-1}e_{1}=\frac{1}{n}\begin{pmatrix}y_{22}&-y_{21}\\\
-y_{12}&y_{11}\end{pmatrix}e_{1}=(y_{22}/n\;\;\;\;-y_{21}/n)^{t}.$

Similarly for $e_{2}$.

Now suppose $n=0$. If (a) holds, then $e_{2}\in H$. If (b) holds, then
$e_{1}\in H$. Conversely, suppose that $X$ has loops, so that $e_{1}\in H$ or
$e_{2}\in H$. First suppose $e_{1}\in H$. Then there exist $r,s\in\mathbb{Z}$
such that

$r\begin{pmatrix}y_{11}\\\ y_{21}\end{pmatrix}+s\begin{pmatrix}y_{12}\\\
y_{22}\end{pmatrix}=e_{1},$ (1)

so $ry_{21}+sy_{22}=0$. Because $n=0$, the left column and right columns of
$M_{X}$ are linearly dependent over $\mathbb{Q}$. Then there exist
$\alpha,\beta\in\mathbb{Z}$, not both $0$, such that

$\alpha\begin{pmatrix}y_{11}\\\
y_{21}\end{pmatrix}=\beta\begin{pmatrix}y_{12}\\\ y_{22}\end{pmatrix}.$ (2)

We can assume $\gcd(\alpha,\beta)=1$, for if not, replace them with
$\alpha/\gcd(\alpha,\beta)$ and $\beta/\gcd(\alpha,\beta)$, respectively.

Then $r\beta y_{21}+s\beta y_{22}=0$, so $r\beta y_{21}+s\alpha y_{21}=0$, so
$r\beta+s\alpha=0$ or $y_{21}=0$.

Case 1: Suppose $r\beta+s\alpha=0$. From (1) we also have $ry_{11}+sy_{12}=1$,
so $\gcd(r,s)=1$. We have $r\beta=-s\alpha$, so $\alpha\mid r$ and $\beta\mid
s$. Also $r\mid\alpha$ and $s\mid\beta$. So either $\alpha=r$ and $\beta=-s$,
or $\alpha=-r$ and $\beta=s$. Either way, (1) and (2) now contradict one
another.

Case 2: Suppose $y_{21}=0$. Then $0=\alpha y_{21}=\beta y_{22}$. If
$y_{22}=0$, then using (1), we find that (b) holds. If not, then $\beta=0$, so
$\alpha\neq 0$, so $y_{11}=y_{21}=0$. Equation (1) then implies that (b)
holds.

A similar argument shows that if $e_{2}\in H$, then (a) must hold.∎

We now have all the pieces in place needed to find $\chi(X)$ whenever $X$ has
an associated $2\times 2$ matrix.

######  Theorem 2.9.

Let $X$ be a standardized abelian Cayley graph defined by

$\begin{pmatrix}y_{11}&0\\\ y_{21}&y_{22}\end{pmatrix}^{\emph{SACG}}_{X}.$

Suppose that $y_{11}\geq 0$ and $y_{22}\geq 0$. Let $d=\gcd(y_{11},y_{21})$
and $e=\gcd(y_{11},y_{21},y_{22})$. Then:

  1. 1.

If either (i) $y_{22}=1$ or (ii) $y_{11}=1$ and $y_{22}|y_{21}$ or (iii)
$y_{11}=0$ and $\gcd(y_{21},y_{22})=1$, then $X$ has loops and is not properly
colorable.

  2. 2.

If both $y_{11}+y_{21}$ and $y_{22}$ are even, then $\chi(X)=2$.

  3. 3.

If (i) neither of the conditions in the previous statements holds, and (ii)
$y_{11}=0$ or $y_{22}=0$ or $e>1$ or $y_{22}|y_{21}$, then $\chi(X)=3$.

  4. 4.

If none of the conditions in the previous statements hold, take
$q\in\mathbb{Z}$ such that $\text{gcd}(y_{11},y_{21}+qy_{22})=1$. (Such a $q$
necessarily exists, as we can let $q$ be the product of all primes $p$ such
that $p|y_{11}$ but $p\nmid d$. Here we adopt the convention that if there are
no such primes, let $q=1$.) Then $\chi(X)=\chi(C_{n}(a,b))$, where
$a=-y_{21}-qy_{22}$, $b=y_{11}$, and $n=y_{11}y_{22}$.

###### Proof.

Lemma 2.8 implies both Statement (1) and its converse. Statement (2) follows
from [1, Lemma LABEL:general-lemma-bipartite].

We now prove Statement (3). Assume that conditions (i) and (ii) in that
statement both hold. Condition (i) implies that $X$ does not have loops, and
that $X$ is not bipartite. If $y_{11}=0$, then we can delete the top row as
per [1, Lemma LABEL:general-lemma-delete-row-all-zeroes] without affecting the
chromatic number. Lemma 2.1 now gives us $\chi(X)=3$. If $y_{22}=0$, then we
can delete the second column as per [1, Lemma LABEL:general-lemma-
isomorphisms(LABEL:general-item-delete-column-Z-span)] without changing $X$.
We then find that $\chi(X)=3$, by [1, Theorem LABEL:general-theorem-tree-
guard]. If $e>1$, then $\chi(X)=3$, by [1, Lemma LABEL:general-lemma-column-
sums-not-coprime]. If $y_{22}|y_{21}$, then after performing a column sum as
in [1, Lemma LABEL:general-lemma-isomorphisms(LABEL:general-item-add-
multiple_of_column)] to eliminate $y_{21}$, by [1, Lemma LABEL:general-lemma-
block-structure], we have that $\chi(X)=3$.

Finally, we prove Statement (4). By [1, Lemma LABEL:general-lemma-
isomorphisms(LABEL:general-item-add-multiple_of_column)], we have that

$\begin{pmatrix}y_{11}&0\\\
y_{21}&y_{22}\end{pmatrix}^{\text{SACG}}_{X}=\begin{pmatrix}y_{11}&0\\\
y_{21}+qy_{22}&y_{22}\end{pmatrix}^{\text{SACG}}_{X}.$

The result follows from Lemma 2.7.∎

It follows from Thm. 2.9 and our previous observations about Heuberger
circulants that for a standardized abelian Cayley graph $X$ with an associated
$2\times 2$ Heuberger matrix, if $X$ does not have loops, then $X$ is
$4$-colorable unless it contains $K_{5}$ as a subgraph; and it is
$3$-colorable unless it contains as a subgraph either a diamond lanyard or
$C_{13}(1,5)$. We will see in §2.5 that this statement holds for the $3\times
2$ case as well.

When $M_{X}$ is a $2\times 2$ matrix, we perform row and column operations to
create a $2\times 2$ lower triangular matrix $M_{X^{\prime}}$ for which
$X^{\prime}$ is isomorphic to $X$. Observing the effect of these operations on
the determinant, we find that $|\det\;M_{X}|=|\det\;M_{X^{\prime}}|$. Note
that in Theorem 2.9, whenever $X$ has no loops and $\chi(X)>3$, we have that
$|\det\;M_{X}|$ is not divisible by $3$. Thus we have the following corollary,
which provides an easily checked sufficient condition for $3$-colorability.

######  Corollary 2.10.

Let $X$ be a standardized abelian Cayley graph with an associated $2\times 2$
matrix $M_{X}$. If $X$ has no loops and $3\mid\det\;M_{X}$, then $\chi(X)\leq
3$.

We note that Cor. 2.10 fails in general for larger matrices. For example, we
have by Thm. 2.9, Thm. 2.6, [1, Lemma LABEL:general-lemma-block-structure],
and Example [1, LABEL:general-example-cycle] that

$\chi\left(\begin{pmatrix}1&0&0\\\ -2&5&0\\\
0&0&3\end{pmatrix}^{\text{SACG}}_{X}\right)=5.$

However, observe that not every $2\times 2$ minor of the matrix above has
determinant divisible by $3$. As mentioned in the introduction, we conjecture
that if this stronger condition holds, and $X$ does not have loops, then $X$
is $3$-colorable.

###  2.4 Modified Hermite normal form

In Subsection 2.3, we saw that it was useful to deal only with $2\times 2$
Heuberger matrices in a certain convenient format. The same goes for $3\times
2$ Heuberger matrices. The crux of this idea is drawn from [4], where Hermite
normal form is used. For $3\times 2$ matrices, we refine the requirements
slightly for our purposes, so as to further reduce the number of exceptional
cases. The purpose of the present subsection is to define this “modified
Hermite normal form” for $3\times 2$ matrices and to show that with very few
exceptions every standardized abelian Cayley graph with an associated $3\times
2$ Heuberger matrix is isomorphic to one with a matrix in this form. We do not
attempt here to generalize these definitions to matrices of arbitrary size, as
we do not know yet what restrictions will prove to be most useful when the
rank or dimension is larger.

######  Definition 2.11.

Let

$M=\begin{pmatrix}y_{11}&y_{12}\\\ y_{21}&y_{22}\\\
y_{31}&y_{32}\end{pmatrix}$

be a $3\times 2$ matrix with integer entries such that no row of $M$ has all
zero entries. We say $M$ is in _modified Hermite normal form_ if the following
conditions hold:

  1. 1.

$y_{11}>0$, and

  2. 2.

$y_{12}=0$, and

  3. 3.

$y_{11}y_{22}\equiv y_{11}y_{32}\;(\textup{mod}\;3)$, and

  4. 4.

$y_{22}\leq y_{32}$, and

  5. 5.

$|y_{22}|\leq|y_{32}|$, and

  6. 6.

Either (i) $y_{22}=0$ and $-\frac{1}{2}|y_{32}|\leq y_{31}\leq 0$, or else
(ii) $-\frac{1}{2}|y_{22}|\leq y_{21}\leq 0$.

There are some departures here from the usual Hermite normal form. For
example, $|y_{21}|$ cannot be more than half of $y_{22}$, a more stringent
requirement than being less than $y_{22}$, as in ordinary Hermite normal form.
As we shall see, we can impose this narrower condition because we have both
row and column operations at our disposal, not just column operations.
Moreover, this form may be the transpose of what some readers are accustomed
to, but we have adopted this convention so as to be consistent with [4]. The
third condition has no analogue with Hermite normal form but will turn out to
be rather useful in the succeeding subsection.

We next show that every standardized abelian Cayley graph with a $3\times 2$
Heuberger matrix of rank 2 without zero rows is isomorphic to one with a
Heuberger matrix in modified Hermite normal form.

######  Lemma 2.12.

Let $X$ be a standardized abelian Cayley graph with a $3\times 2$ Heuberger
matrix $M_{X}$. Suppose that $M_{X}$ has no zero rows, and that the columns of
$M_{X}$ are linearly independent over $\mathbb{Q}$. Then $X$ is isomorphic to
a standardized abelian Cayley graph $X^{\prime}$ with a $3\times 2$ Heuberger
matrix $M_{X^{\prime}}$ in modified Hermite normal form.

###### Proof.

The proof is constructive. We give an explicit algorithm for row and column
operations to perform on $M_{X}$, as per [1, Lemma LABEL:general-lemma-
isomorphisms], so as to result in the desired matrix $M_{X^{\prime}}$.

  1. Step Zero:

Let $\alpha,\beta$, and $\gamma$ be the determinants of the $2\times 2$ minors
of $M_{X}$. Two of $\alpha,\beta,\gamma$ must be congruent to each other or
negatives of each other modulo $3$. Using this fact, we can permute rows
and/or multiply rows by $-1$ as needed so that the determinant of the
submatrix formed by the top two rows is congruent modulo $3$ to the submatrix
formed by the first and third rows. This property will be preserved by all
subsequent steps and will eventually lead to satisfaction of the third
condition in Def. 2.11. Let $M_{X_{1}}$ be the resulting matrix.

  2. Step One:

If the first entry of any column of $M_{X_{1}}$ is negative, multiply that
column (or those columns) by $-1$. Let $M_{X_{2}}$ be the resulting matrix.
The top row of $M_{X_{2}}$ has no negative entries.

  3. Step Two:

If the first entry of the first column of $M_{X_{2}}$ is $0$, then permute the
two columns; otherwise, do nothing. Let $M_{X_{3}}$ be the resulting matrix.
The first entry of the first column of $M_{X_{3}}$ is strictly positive. (Here
is where we use the assumption that $M_{X}$ has no zero rows.) If the first
entry of the second column is $0$, then let $M_{X_{4}}=M_{X_{3}}$ and skip to
Step Four.

  4. Step Three:

Both entries of the top row of $M_{X_{3}}$ are strictly positive. Let $e$ be
the greatest common divisor of these two entries. Repeatedly applying [1,
Lemma LABEL:general-lemma-isomorphisms(LABEL:general-item-add-
multiple_of_column)], we perform column operations that effectuate the
Euclidean algorithm on the entries in the top row of $M_{X_{3}}$, so that the
top row of the resulting matrix has two entries, one of which is $e$, the
other $0$. If the first entry of the first column is $0$, then permute the two
columns. Let $M_{X_{4}}$ be the resulting matrix. The top row of $M_{X_{4}}$
has a strictly positive first entry, and $0$ for its second entry. The matrix
$M_{X_{4}}$ now meets the first three conditions in the definition of modified
Hermite normal form, and these will be preserved by all subsequent steps.

  5. Step Four:

Let $z$ and $w$ be the $(3,1)$ and $(3,2)$ entries of $M_{X_{4}}$,
respectively. If $z\leq w$ and $|z|\leq|w|$, then do nothing. If $z>w$ and
$|z|\leq|w|$, then multiply the second column by $-1$. If $z\leq w$ and
$|z|>|w|$, then switch the bottom two rows and multiply the second column by
$-1$. If $z>w$ and $|z|>|w|$, then switch the bottom two rows. Whatever action
was taken, let $M_{X_{5}}$ be the resulting matrix. The first five conditions
in Def. 2.11 are now (and will continue to be) met.

  6. Step Five:

Let $a$ and $b$ be the $(2,1)$ and $(2,2)$ entries of $M_{X_{5}}$,
respectively. If $b=0$, then apply to the third rather than second row the
procedure described in the rest of Step Five as well as in Step Six. (Here is
where we use that the columns of $M_{X}$ are linearly independent over
$\mathbb{Q}$; this guarantees that if $b=0$, then the $(3,2)$ entry of
$M_{X_{5}}$ is not zero.) If $b\neq 0$, by the division theorem, there exist
integers $q$ and $r$ such that $r=a-q|b|$, where $-|b|<r\leq 0$. Applying [1,
Lemma LABEL:general-lemma-isomorphisms(LABEL:general-item-add-
multiple_of_column)], perform a column operations to replace the first column
with the first column plus $\pm q$ times the second column, so that the second
entry in the first column becomes $r$. Let $M_{X_{6}}$ be the resulting
matrix.

  7. Step Six:

Let $c$ be the $(2,1)$ entry of $M_{X_{6}}$. We still have that $b$ is the
$(2,2)$ entry of $M_{X_{6}}$. Suppose that $-\frac{|b|}{2}>c$. We then add
$b/|b|$ times the second column to the first column; then multiply the first
column by $-1$; and then multiply the first row by $-1$. Let $M_{X^{\prime}}$
be the resulting matrix.

The matrix $M_{X^{\prime}}$ will then satisfy all conditions in the definition
of modified Hermite normal form.∎

Suppose we have a $3\times 2$ Heuberger matrix $M_{X}$. If $M_{X}$ has a zero
row, then by [1, Lemma LABEL:general-lemma-delete-row-all-zeroes], we can
delete it without affecting the chromatic number $\chi$, whereupon Thm. 2.9
can be used to find $\chi$. If the columns of $M_{X}$ are linearly dependent
over $\mathbb{Q}$, then as per [1, Lemma LABEL:general-lemma-isomorphisms]
appropriate column operations that do not change $X$ will produce a zero
column, which can be deleted without changing $X$. [1, Thm. LABEL:general-
theorem-tree-guard] can then be used to find $\chi(X)$. Otherwise, in light of
Lemma 2.12, we lose no generality by assuming that $M_{X}$ is in modified
Hermite normal form.

We next show that when $M_{X}$ is in modified Hermite normal form, we can
determine immediately whether $X$ has loops. Recall that $e_{j}$ is the $j$th
standard basis vector, with a $1$ as its $j$th entry and $0$ for every other
entry.

######  Lemma 2.13.

Let $X$ be a standardized abelian Cayley graph with a Heuberger matrix
$M_{X}$. Suppose that $M_{X}$ is a $3\times 2$ matrix in modified Hermite
normal form. Then $X$ has loops if and only if either the first column of
$M_{X}$ is $e_{1}$, or the second column of $M_{X}$ is $e_{3}$.

###### Proof.

Let $H$ be the $\mathbb{Z}$-span of the columns of $M_{X}$. The graph $X$ has
loops if and only if $\pm e_{j}\in H$ for some $j$. From the definition of
modified Hermite normal form, we see that this can occur if and only if either
the first column of $M_{X}$ is $e_{1}$ or the second column of $M_{X}$ is
$e_{3}$. ∎

###  2.5 Chromatic numbers of graphs with $3\times 2$ matrices in modified
Hermite normal form

In this section we prove the following theorem, which completely determines
the chromatic number of an arbitrary standardized abelian Cayley graph with a
$3\times 2$ Heuberger matrix in modified Hermite normal form.

######  Theorem 2.14.

Let $X$ be a standardized abelian Cayley graph with a Heuberger matrix

$M_{X}=\begin{pmatrix}y_{11}&0\\\ y_{21}&y_{22}\\\ y_{31}&y_{32}\\\
\end{pmatrix}$

in modified Hermite normal form.

  1. 1.

If the first column of $M_{X}$ is $e_{1}$ or the second column of $M_{X}$ is
$e_{3}$, then $X$ has loops and cannot be properly colored.

  2. 2.

If $y_{11}+y_{21}+y_{31}$ and $y_{22}+y_{32}$ are both even, then $\chi(X)=2$.

  3. 3.

If

$M_{X}=\begin{pmatrix}1&0\\\ 0&1\\\ \pm 3k&1+3k\end{pmatrix}\text{ or
}M_{X}=\begin{pmatrix}1&0\\\ 0&-1\\\ \pm 3k&-1+3k\end{pmatrix}\text{ or
}M_{X}=\begin{pmatrix}1&0\\\ -1&2\\\ -1-3k&2+3k\end{pmatrix}\text{ or
}M_{X}=\begin{pmatrix}1&0\\\ -1&-2\\\ -1+3k&-2+3k\end{pmatrix}$

$\text{ for some positive integer }k,\text{ or }M_{X}=\begin{pmatrix}1&0\\\
0&-1\\\ 3b&2\end{pmatrix}\text{ for some integer }b,\text{ or}$

$M_{X}=\begin{pmatrix}1&0\\\ -1&a\\\ -1&a+3(k-1)\end{pmatrix}\text{ for some
integer }a\text{ with }3\nmid a\text{ and some positive integer }k,$

then $\chi(X)=4$.

  4. 4.

If none of the above conditions hold, then $\chi(X)=3$.

The main idea behind the proof of Theorem 2.14 is to add or subtract two rows
as per [1, Lemma LABEL:general-lemma-homomorphisms] to obtain a homomorphism
from $X$ to a graph with a $2\times 2$ Heuberger matrix. Theorem 2.9 and its
corollary provide conditions under which this latter graph (and hence $X$) is
$3$-colorable. If those conditions are not met, then we get information about
$M_{X}$. In this case we can repeat the procedure using some other
homomorphism to further narrow down the possibilities for those $M_{X}$ for
which $\chi(X)>3$. In particular, we are led in this way to consider three
special types of matrices $M_{X}$: those with $y_{22}=0$ (we call these
“L-shaped” matrices); those with $y_{11}=y_{22}=1$ and $y_{21}=0$ (we call
these “$I$ on top” matrices); and those with $y_{11}=y_{21}=y_{31}=1$ (we call
these “first column all ones” matrices). Every exceptional case traces back
ultimately to one of these three. Hence, to lay the groundwork for the proof
of Theorem 2.14, we first prove three technical lemmas which compute the
chromatic numbers in these three circumstances. The proofs of all three use
the same main idea: Add or subtract rows to map to a graph with a $2\times 2$
matrix. If such maps fail to produce a $3$-coloring, then show that $X$
contains a diamond lanyard.

We begin with “first column all ones” matrices.

######  Lemma 2.15.

Suppose we have

$\begin{pmatrix}1&&0\\\ 1&&y_{22}\\\
1&&y_{32}\end{pmatrix}^{\text{SACG}}_{X}.$

Then $X$ has loops if and only if $\\{y_{22},y_{32}\\}$ is $\\{0,-1\\}$ or
$\\{0,1\\}$ or $\\{-1\\}$ or $\\{1\\}$. Otherwise,

$\chi(X)=\begin{cases}3&\text{ if }y_{32}\equiv-y_{22}\;(\textup{mod}\;3)\\\
4&\text{ if }y_{32}\not\equiv-y_{22}\;(\textup{mod}\;3).\end{cases}$

###### Proof.

The statement about loops is straightforward. Now suppose that $X$ does not
have loops. Let $M_{X}$ be the matrix in the lemma statement.

The first column’s sum is odd, so $X$ cannot be bipartite, by [1, Lemma
LABEL:general-lemma-bipartite].

If $y_{32}\equiv-y_{22}\;(\textup{mod}\;3)$, then we get $\chi(X)=3$ by
applying [1, Lemma LABEL:general-lemma-column-sums-not-coprime].

Now assume that $y_{32}\not\equiv-y_{22}\;(\textup{mod}\;3)$, in other words
that $y_{32}=-y_{22}\pm 1+3\ell$ for some integer $\ell$. First we show that
$\chi(X)>3$, by showing that $X$ contains a diamond lanyard. Let $H$ be the
subgroup of $\mathbb{Z}^{3}$ generated by the columns of $M_{X}$. Recall that
vertices of $X$ are of the form $(a,b,c)^{t}+H$, which we denote by
$\overline{(a,b,c)^{t}}$. The vertices
$\overline{(0,0,0)^{t}},\overline{(0,1,0)^{t}},\overline{(0,0,-1)^{t}},$ and
$\overline{(0,1,-1)^{t}}$ form a diamond in $X$. Shifting this diamond $x-1$
times by $\overline{(0,1,-1)^{t}}$ and concatenating, we produce an unclasped
diamond lanyard $L_{1}$ of length $x$ with endpoints $\overline{(0,0,0)^{t}}$
and $\overline{(0,x,-x)^{t}}$. In a similar vein, we have an unclasped diamond
lanyard of length $2$ formed by one diamond with vertices
$\overline{(0,0,0)^{t}},\overline{(0,1,0)^{t}},\overline{(0,1,1)^{t}},$ and
$\overline{(0,2,1)^{t}}$ and another diamond with vertices
$\overline{(0,2,1)^{t}},\overline{(0,2,0)^{t}},\overline{(0,3,1)^{t}},$ and
$\overline{(0,3,0)^{t}}$. Its endpoints are $\overline{(0,0,0)^{t}}$ and
$\overline{(0,3,0)^{t}}$. Assume for now that $\ell\geq 1$. Shifting $\ell-1$
times by $\overline{(0,3,0)^{t}}$ and concatenating, we produce an unclasped
diamond lanyard $L_{2}$ of length $2\ell$ with endpoints
$\overline{(0,0,0)^{t}}$ and $\overline{(0,3\ell,0)^{t}}$. Conjoining $L_{1}$
and $L_{2}$ gives us an unclasped diamond lanyard of length $x+2\ell$ with
endpoints $\overline{(0,x,-x)^{t}}$ and $\overline{(0,3\ell,0)^{t}}$. Taking
$x=\pm 1+y_{22}+3\ell$ produces an edge between $\overline{(0,x,-x)^{t}}$ and
$\overline{(0,3\ell,0)^{t}}$, and thus we have a clasped diamond lanyard in
$X$. By Lemma 2.3, we have that $\chi(X)\geq 4$. A similar procedure gives the
same result when $\ell\leq 0$.

Now we show that $\chi(X)\leq 4$. By [1, Lemma LABEL:general-lemma-
homomorphisms] we have a homomorphism

$\begin{pmatrix}1&&0\\\ 1&&y_{22}\\\
1&&y_{32}\end{pmatrix}_{X}^{\text{SACG}}\xrightarrow{\ocirc}\begin{pmatrix}1&&0\\\
2&&y_{22}+y_{32}\end{pmatrix}_{Y}^{\text{SACG}}.$

The results of §2.3 imply that we fail to get a $4$-coloring if and only if
$y_{22}+y_{32}\in\\{-5,-2,-1,1,2,5\\}$.

First we consider the case where $y_{22}+y_{32}=-5$. Then

$\begin{pmatrix}1&&0\\\ 1&&y_{22}\\\
1&&-y_{22}-5\end{pmatrix}_{X}^{\text{SACG}}\xrightarrow{\ocirc}\begin{pmatrix}2&&-y_{22}-5\\\
1&&y_{22}\end{pmatrix}^{\text{SACG}}\cong\begin{pmatrix}1&&0\\\
2&&3y_{22}+5\end{pmatrix}_{Y^{\prime}}^{\text{SACG}}.$

Here we use [1, Lemmas LABEL:general-lemma-homomorphisms and LABEL:general-
lemma-isomorphisms], and from now on we shall do this sort of thing without
referring to these lemmas each time. By Theorem 2.9, we have that $Y^{\prime}$
is $4$-colorable unless $y_{22}=-1$. But in that case we have:

$\begin{pmatrix}1&&0\\\ 1&&-1\\\
1&&-4\end{pmatrix}_{X}^{\text{SACG}}\xrightarrow{\ocirc}\begin{pmatrix}2&&-1\\\
1&&-4\end{pmatrix}^{\text{SACG}}\cong C_{7}(1,4),$

which is $4$-colorable. Here we use Theorems 2.9 and 2.6 as well as Lemma 2.7.
In the sequel, usually we will simply compute chromatic numbers of graphs with
$2\times 2$ matrices using the results of §2.3 without referring to the
specific theorems and lemmas used.

The other cases, where $y_{22}+y_{32}$ equals $-2$ or $-1$ or $1$ or $2$ or
$5$, can each be dealt with in a similar way. We omit the proofs here, but
complete details can be found in our authors’ notes, which are housed on the
second author’s website [3].∎

Next we tackle “L-shaped” matrices. By performing row and column operations
not unlike those in §2.4, it suffices to consider only matrices with some
additional restrictions imposed.

######  Lemma 2.16.

Suppose we have

$\begin{pmatrix}y_{11}&&0\\\ y_{21}&&0\\\
y_{31}&&y_{32}\end{pmatrix}^{\text{SACG}}_{X},$

where $y_{11},y_{21},y_{32}>0$ and $-\frac{y_{32}}{2}\leq y_{31}\leq 0$.

Then:

  1. 1.

We have that $X$ has loops if and only if $y_{32}=1$.

  2. 2.

We have that $\chi(X)=2$ if and only if $y_{11}+y_{21}+y_{31}$ and $y_{32}$
are both even.

  3. 3.

We have that $\chi(X)=4$ if and only if $y_{11}=y_{21}=-y_{31}=1$ and $3\nmid
y_{32}$ and $y_{32}>1$.

  4. 4.

Otherwise, $\chi(X)=3$.

###### Proof.

The first two statements are straightforward to prove. Now suppose that $X$
does not have loops (i.e., that $y_{32}\geq 2$) and is not bipartite. Let
$M_{X}$ be the matrix in the lemma statement. We have that $3$ divides either
$y_{11}$, $y_{21}$, $y_{11}+y_{21}$, or $y_{11}-y_{21}$, and we divvy into
cases accordingly.

First suppose that $3\mid y_{11}$. We have

$\begin{pmatrix}y_{11}&&0\\\ y_{21}&&0\\\
y_{31}&&y_{32}\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}y_{11}&&0\\\
y_{21}+y_{31}&&y_{32}\end{pmatrix}^{\text{SACG}}_{Y}.$

We see that $3\mid\det M_{Y}$, where $M_{Y}$ is the Heuberger matrix for $Y$
shown above. By Cor. 2.10, it follows that $Y$ is $3$-colorable unless it has
loops. But this cannot happen, because $3\mid y_{11}$ and $y_{11}>0$ and
$y_{32}\geq 2$.

The case where $3\mid y_{21}$ is handled similarly, as is the case where
$3\mid y_{11}+y_{21}$; in this latter case, begin with a homomorphism that
“collapses” the top two rows by adding them.

Finally, suppose that $3\mid y_{11}-y_{21}$. We may assume without loss of
generality that $y_{11}\geq y_{21}$, for if not, then swap the top two rows.
We have

$\begin{pmatrix}y_{11}&&0\\\ y_{21}&&0\\\
y_{31}&&y_{32}\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}y_{11}-y_{21}&&0\\\
y_{31}&&y_{32}\end{pmatrix}^{\text{SACG}}_{Y}.$

By Cor. 2.10, it follows that $Y$ is $3$-colorable unless it has loops.
Because $y_{32}\geq 2$ and $3\mid y_{11}-y_{21}$, this occurs if and only if
(i) $y_{11}-y_{21}=1$ and $y_{32}\mid y_{31}$, or (ii) $y_{11}-y_{21}=0$ and
$\text{gcd}(y_{31},y_{32})=1$.

Suppose (i) occurs. By our assumption that $-\frac{y_{32}}{2}\leq y_{31}\leq
0$, we must have that $y_{31}=0$. But then by [1, Lemma LABEL:general-lemma-
block-structure, Theorem LABEL:general-theorem-tree-guard, and Example
LABEL:general-example-cycle], we have that $X$ is $3$-colorable.

Now suppose that (ii) occurs. Let $\alpha,\beta\in\mathbb{Z}$ such that
$\alpha y_{31}+\beta y_{32}=1$. Multiply $M_{X}$ on the right by the
unimodular matrix

$\begin{pmatrix}\alpha&-y_{32}\\\ \beta&y_{31}\end{pmatrix}$

to get

$\begin{pmatrix}y_{11}&0\\\ y_{11}&0\\\
y_{31}&y_{32}\end{pmatrix}^{\text{SACG}}_{X}=\begin{pmatrix}\alpha
y_{11}&-y_{11}y_{32}\\\ \alpha y_{11}&-y_{11}y_{32}\\\
1&0\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}1&0\\\
-2\alpha y_{11}&2y_{11}y_{32}\end{pmatrix}^{\text{SACG}}_{Y^{\prime}}$

Provided $Y^{\prime}$ does not have loops, $Y^{\prime}$ is isomophic to the
Heuberger circulant $C_{n^{\prime}}(a^{\prime},b^{\prime})$ with
$n^{\prime}=2y_{11}y_{32}$, $a^{\prime}=2\alpha y_{11}$, $b^{\prime}=1$. So
$Y^{\prime}$ is $3$-colorable unless it has loops or one of the exceptional
cases in Theorem 2.6 occurs. We now deal with these possibilities one at a
time.

Suppose $Y^{\prime}$ has loops. Because $y_{11}>0$ and $y_{32}\geq 2$, this
occurs if and only if $2y_{11}y_{32}\mid 2\alpha y_{11}$, which happens if and
only if $y_{32}\mid\alpha$. But then using column operations, we get that $X$
has loops, contrary to our assumptions. Observe that $n^{\prime}=\pm 5$ and
$n^{\prime}=\pm 13$ cannot happen, because $n^{\prime}$ is even. In the
remaining cases, we show $y_{11}=1$, then we proceed from there. Suppose
$a^{\prime}\equiv\pm 2b^{\prime}\;(\textup{mod}\;n^{\prime})$. So $2\alpha
y_{11}\equiv\pm 2\;(\textup{mod}\;2y_{11}y_{32})$. So $\alpha y_{11}\equiv\pm
1\;(\textup{mod}\;y_{11}y_{32})$. So $y_{11}\mid\pm 1$, which implies
$y_{11}=1$. Suppose $2a^{\prime}\equiv\pm b^{\prime}\;(\textup{mod}\;n)$. So
$4\alpha y_{11}\equiv\pm 1\;(\textup{mod}\;2y_{11}y_{32})$. So $y_{11}\mid\pm
1$, which implies $y_{11}=1$.

Thus we have:

$\begin{pmatrix}1&0\\\ 1&0\\\
y_{31}&y_{32}\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}1&0\\\
y_{31}+1&y_{32}\end{pmatrix}^{\text{SACG}}_{Y^{\prime\prime}}$

Then $Y^{\prime\prime}$ has loops if and only if $y_{32}\mid y_{31}+1$. But
then $y_{31}=ky_{32}-1$ for some integer $k$. From our assumption that
$-\frac{y_{32}}{2}\leq y_{31}\leq 0$, we must have that $k=0$ and $y_{31}=-1$.
The conclusion of the lemma now follows in this case from Lemma 2.15.

So now we can assume that $y_{31}<-1$. Then by Lemma 2.7, we have that
$Y^{\prime\prime}$ is isomorphic to the Heuberger ciculant
$C_{n^{\prime\prime}}(a^{\prime\prime},b^{\prime\prime})$ with
$n^{\prime\prime}=y_{32}$, $a^{\prime\prime}=-y_{31}-1$, $b^{\prime\prime}=1$.
Suppose $Y^{\prime\prime}$ is not $3$-colorable. So one of the exceptional
cases in Theorem 2.6 occurs. We now deal with these possibilities one at a
time.

» Suppose that $n^{\prime\prime}=5$ and $a^{\prime\prime}\equiv\pm
2b^{\prime\prime}\;(\textup{mod}\;5)$. Then $y_{32}=5$ and
$a^{\prime\prime}\equiv 2$ or $3$ mod $5$. Hence $y_{31}=-2$, using that
$-\frac{y_{32}}{2}\leq y_{31}\leq 0$ as well as that $y_{31}<-1$. But then

$\begin{pmatrix}1&0\\\ 1&0\\\
-2&5\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}1&0\\\
-1&5\end{pmatrix}^{\text{SACG}}$

gives us a $3$-coloring of $X$.

» Suppose $n^{\prime\prime}=13$ and one of $a^{\prime\prime}$ or
$b^{\prime\prime}$ is congruent to $\pm 5$ times the other modulo $13$: Then
$y_{32}=13$ and $a^{\prime\prime}\equiv 5$ or $8$ modulo $13$. From
$-\frac{y_{32}}{2}\leq y_{31}\leq 0$ and $y_{31}<-1$ and
$a^{\prime\prime}=-y_{31}-1$, we get $y_{31}=-6$. But then

$\begin{pmatrix}1&0\\\ 1&0\\\
-6&13\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}2&0\\\
-6&13\end{pmatrix}^{\text{SACG}}\xrightarrow{\ocirc}\begin{pmatrix}1&0\\\
-3&13\end{pmatrix}^{\text{SACG}}$

gives us a map to a $3$-colorable Heuberger circulant.

» Suppose $a^{\prime\prime}\equiv
2b^{\prime\prime}\;(\textup{mod}\;n^{\prime\prime})$. Then $y_{32}\mid
y_{31}+3$. Note we cannot have $y_{31}=-2$, since then $y_{32}\mid 1$, but
$y_{32}>1$.

If $y_{31}=-3$, then we have

$\begin{pmatrix}1&0\\\ 1&0\\\
-3&y_{32}\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}2&0\\\
-3&y_{32}\end{pmatrix}^{\text{SACG}}_{Z}$

The graph $Z$ cannot have loops. Let $a=3,b=2,n=2y_{32}$. Then $Z$ is
isomorphic to the Heuberger circulant $C_{n}(a,b)$. We cannot have $n=5$ or
$n=13$, because $n$ is even. If $a\equiv 2b\;(\textup{mod}\;n)$, then
$2y_{32}\mid-1$, which cannot happen. If $a\equiv-2b\;(\textup{mod}\;n)$, then
$2y_{32}\mid 7$, which cannot happen. If $2a\equiv b\;(\textup{mod}\;n)$, then
$2y_{32}\mid 4$, which implies that $y_{32}=2$, but this violates
$-\frac{y_{32}}{2}\leq y_{31}\leq 0$. If $2a\equiv-b\;(\textup{mod}\;n)$, then
$2y_{32}\mid 8$, which implies that $y_{32}=2$ or $y_{32}=4$, both of which
violate $-\frac{y_{32}}{2}\leq y_{31}\leq 0$.

Now assume $y_{31}<-3$, which implies that $y_{31}+3<0$. So from $y_{32}\mid
y_{31}+3$, we get that $y_{32}\leq-3-y_{31}\leq-3+\frac{y_{32}}{2}$. But
$y_{32}>0$, so this cannot happen.

» Suppose that
$a^{\prime\prime}\equiv-2b^{\prime\prime}\;(\textup{mod}\;n^{\prime\prime})$.
Then $y_{32}\mid y_{31}-1$. So $y_{32}\leq 1-y_{31}\leq 1+\frac{y_{32}}{2}$.
But $y_{32}>1$.

» Suppose that $2a^{\prime\prime}\equiv
b^{\prime\prime}\;(\textup{mod}\;n^{\prime\prime})$. Then $y_{32}\mid
2y_{31}+3$. Because $y_{31}\leq-2$, we have $2y_{31}+3<0$. Hence
$y_{32}\leq-2y_{31}-3\leq y_{32}-3$, which is a contradiction.

» Suppose that
$2a^{\prime\prime}\equiv-b^{\prime\prime}\;(\textup{mod}\;n^{\prime\prime})$.
Then $y_{32}\mid 2y_{31}+1$. So $y_{32}\leq-2y_{31}-1\leq y_{32}-1$, which is
a contradiction.∎

In our final preparatory step, we contemplate “$I$ on top” matrices. As
before, we obtain upper bounds by mapping to graphs with $2\times 2$ matrices,
and we obtain a lower bound in some cases by finding diamond lanyards as
subgraphs.

######  Lemma 2.17.

Suppose $X$ is a standardized abelian Cayley graph with an associated
Heuberger matrix

$M_{X}=\begin{pmatrix}1&0\\\ 0&1\\\ y_{31}&y_{32}\end{pmatrix},$

where $y_{31},y_{32}>0$ and $y_{31}\leq y_{32}$. Then

$\chi(X)=\begin{cases}2&\text{if }y_{31}\text{ and }y_{32}\text{ are both
odd}\\\ 4&\text{if }y_{31}=2\text{ and }3\mid y_{32}\\\ 4&\text{if
}1\not\equiv y_{31}\;(\textup{mod}\;3)\text{ and }y_{32}=1+y_{31}\\\
3&\text{otherwise}.\par\end{cases}$

Before embarking on the proof, we note that by [1, Example LABEL:general-
example-arbitrary-distance-graph], we have that $X$ is isomorphic to the
distance graph $\text{Cay}(\mathbb{Z},\\{\pm 1,\pm y_{31},\pm y_{32}\\})$.
Hence Lemma 2.17 is a special case of Zhu’s theorem, as discussed in [2]. We
offer here an alternative proof using Heuberger matrices.

###### Proof.

[1, Lemma LABEL:general-lemma-bipartite] implies that $\chi(X)=2$ if and only
if $y_{31}$ and $y_{32}$ are both odd.

To show that $X$ is $4$-colorable, consider

$\begin{pmatrix}1&0\\\ 0&1\\\
y_{31}&y_{32}\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}1&0\\\
y_{31}&1+y_{32}\end{pmatrix}^{\text{SACG}}_{Y}$

By Lemma 2.8 and 2.7, we see that $Y$ does not contain loops and is isomorphic
to the Heuberger circulant $C_{1+y_{32}}(1,y_{31})$. So $Y$ is $4$-colorable
unless $y_{32}=4$ and $y_{31}\in\\{2,3\\}$. But in these cases respectively
take

$\begin{pmatrix}1&0\\\ 0&1\\\
2&4\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}1&0\\\
2&3\end{pmatrix}^{\text{SACG}}\text{ and }\begin{pmatrix}1&0\\\ 0&1\\\
3&4\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}1&-1\\\
3&4\end{pmatrix}^{\text{SACG}}.$

Indeed, $Y$ is $3$-colorable unless one of the six exceptional cases in
Theorem 2.6 occurs. Those cases each place restrictions on $y_{31}$ and
$y_{32}$, whereupon we can modify the mapping appropriately to try to get a
$3$-coloring. One can show that this procedure will produce a $3$-coloring
unless either $y_{31}=2$ and $3\mid y_{32}$, or else $1\not\equiv
y_{31}\;(\textup{mod}\;3)$ and $y_{32}=1+y_{31}$. The logic is quite similar
to that in the proofs of Lemmas 2.15 and 2.16, so we omit it here. Complete
details can be found in our authors’ notes, which are housed on the second
author’s website [3].

Finally, we show that if either $y_{31}=2$ and $3\mid y_{32}$, or else
$1\not\equiv y_{31}\;(\textup{mod}\;3)$ and $y_{32}=1+y_{31}$, then $X$
contains a diamond lanyard. By Lemma 2.3, this will show that $\chi(X)\geq 4$
in these cases. We note that this is essentially what Zhu does in [8] to find
a lower bound on the fractional chromatic number of distance graphs such as
these. Let $H$ be the subgroup of $\mathbb{Z}^{3}$ generated by the columns of
$M_{X}$. We denote by $\overline{(a,b,c)^{t}}$ the vertex $(a,b,c)^{t}+H$ of
$X$.

Suppose $y_{31}=2$ and $3\mid y_{32}$. We have that $y_{32}=3k\pm 1$ for some
positive integer $k$. There is a diamond in $X$ with vertices
$\overline{(0,0,0)^{t}},\overline{(0,0,1)^{t}},\overline{(0,0,2)^{t}}$, and
$\overline{(0,0,3)^{t}}$. Shifting this $k-1$ times by
$\overline{(0,0,3)^{t}}$ and concatenating, we obtain a diamond lanyard of
length $k$ with endpoints $\overline{(0,0,0)^{t}}$ and
$\overline{(0,0,3k)^{t}}$.

Now suppose that $1\not\equiv y_{31}\;(\textup{mod}\;3)$ and
$y_{32}=1+y_{31}$. So either $y_{31}$ or $y_{32}$ equals $3k$ for some
positive integer $k$. We have a diamond in $X$ with vertices
$\overline{(0,0,0)^{t}},\overline{(0,0,1)^{t}},\overline{(0,0,y_{32})^{t}}$,
and $\overline{(0,0,y_{32}+1)^{t}}$. Shifting this by
$\overline{(0,0,y_{32}+1)^{t}}$, we obtain an unclasped diamond lanyard of
length two with endpoints $\overline{(0,0,0)^{t}}$ and
$\overline{(0,0,2y_{32}+2)^{t}}$. Append to this a diamond with vertices
$\overline{(0,0,2y_{32}+2)^{t}},\overline{(0,0,y_{32}+3)^{t}},\overline{(0,0,y_{32}+2)^{t}}$,
and $\overline{(0,0,3)^{t}}$. We thus obtain an unclasped diamond lanyard of
length three with endpoints $\overline{(0,0,0)^{t}}$ and
$\overline{(0,0,3)^{t}}$. Shifting this $k-1$ times by
$\overline{(0,0,3)^{t}}$ and concatenating, we obtain a diamond lanyard of
length $3k$ with endpoints $\overline{(0,0,0)^{t}}$ and
$\overline{(0,0,3k)^{t}}$. ∎

Finally, we turn our attention to proving Theorem 2.14. The essense of the
proof is to show that if we do not have a homomorphism from $X$ to a
$3$-colorable graph with a $2\times 2$ matrix, then $M_{X}$ must be in a form
where (perhaps after some manipulations) one of the preceding three lemmas
applies.

###### Proof of Theorem 2.14.

The first statement follows from Lemma 2.13, and the second follows from [1,
Lemma LABEL:general-lemma-bipartite].

Now suppose that $M_{X}$ is one of the six types of matrices listed in the
third statement. Lemma 2.17 shows that if $M_{X}$ is of the form
$\begin{pmatrix}1&0\\\ 0&1\\\ 3k&1+3k\end{pmatrix}$, then $\chi(X)=4$. For the
other five, we can perform row and column operations as per [1, Lemma
LABEL:general-lemma-isomorphisms] to obtain a matrix for an isomorphic graph
so that either Lemma 2.17 or 2.15 proves the third statement of the corollary.
For example, suppose $M_{X}$ is of the form $\begin{pmatrix}1&0\\\ -1&2\\\
-1-3k&2+3k\end{pmatrix}$ for an integer $k$. Add the second column to the
first and then multiply the third row by $-1$ to produce the matrix
$\begin{pmatrix}1&0\\\ 1&2\\\ 1&-2-3k\end{pmatrix},$ whereupon Lemma 2.15
applies. We leave the computations in the other four cases to the reader.

Finally, assume that none of the first three statements apply. We will show
that $X$ has a $3$-coloring.

Take the following mapping:

$\begin{pmatrix}y_{11}&0\\\ y_{21}&y_{22}\\\
y_{31}&y_{32}\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}y_{11}&0\\\
y_{21}-y_{31}&y_{22}-y_{32}\end{pmatrix}^{\text{SACG}}_{Y}$

Let $M_{Y}$ be the $2\times 2$ matrix given above for $Y$. From Def. 2.11 we
have that $3\mid\det M_{Y}$. So by Cor. 2.10, we have that $Y$ (and hence $X$)
is $3$-colorable unless $Y$ has loops. (We remark that we imposed the third
condition in Def. 2.11 specifically so that we can use Cor. 2.10 right here.)
By Lemma 2.8 and Def. 2.11, we have that either (i) $y_{22}-y_{32}=-1$, or
(ii) $y_{11}=1$ and $y_{22}-y_{32}\mid y_{21}-y_{31}$.

Suppose (i) holds. Because $3\mid\det M_{Y}$, we must have that $3\mid
y_{11}$. Now consider

$\begin{pmatrix}y_{11}&0\\\ y_{21}&y_{22}\\\
y_{31}&y_{32}\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}y_{11}&0\\\
y_{21}+y_{31}&y_{22}+y_{32}\end{pmatrix}^{\text{SACG}}$

By Cor. 2.10, this produces a $3$-coloring unless the target graph has loops.
But by Lemma 2.8, this occurs if and only if $y_{22}+y_{32}=\pm 1$, which
gives us that $y_{22}=0$ and $y_{32}=1$. But then the first statement in the
theorem holds, contrary to assumption.

Thus (ii) holds. Because $3\mid\det M_{Y}$, we must have $y_{32}=y_{22}+3k$
for some integer $k\geq 0$. (Here we use that $y_{32}\geq y_{22}$.) Also
$\ell(y_{22}-y_{32})=y_{21}-y_{31}$ for some integer $\ell$, which gives us
that $y_{31}=y_{21}+3k\ell$. So we have

$M_{X}=\begin{pmatrix}1&0\\\ y_{21}&y_{22}\\\
y_{21}+3k\ell&y_{22}+3k\end{pmatrix}.$ (3)

Take the mapping

$\begin{pmatrix}1&0\\\ y_{21}&y_{22}\\\
y_{21}+3k\ell&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}1&0\\\
2y_{21}+3k\ell&2y_{22}+3k\end{pmatrix}^{\text{SACG}}_{Y^{\prime}}.$

Either $Y^{\prime}$ has loops, or else by Lemma 2.7 we have that $Y^{\prime}$
is isomorphic to the Heuberger circulant
$C_{n^{\prime}}(a^{\prime},b^{\prime})$ with $n^{\prime}=2y_{22}+3k$ and
$a^{\prime}=-2y_{21}-3k\ell$ and $b^{\prime}=1$.

» First suppose that $Y^{\prime}$ has loops. By Lemma 2.8, this occurs if and
only if $2y_{22}+3k\mid 2y_{21}+3k\ell$. Then $2y_{21}+3k\ell=(2y_{22}+3k)q$
for some $q\in\mathbb{Z}$. So $y_{21}=qy_{22}+\frac{3}{2}k(q-\ell)$. Letting
$t=q-\ell$, by various columm operations we have

$\displaystyle\begin{pmatrix}1&&0\\\ y_{21}&&y_{22}\\\
y_{21}+3k\ell&&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}$
$\displaystyle=\begin{pmatrix}1&&0\\\ qy_{22}+\frac{3}{2}k(q-\ell)&&y_{22}\\\
qy_{22}+\frac{3}{2}k(q+\ell)&&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}=\begin{pmatrix}1&&0\\\
\frac{3}{2}k(q-\ell)&&y_{22}\\\
\frac{3}{2}k(-q+\ell)&&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}$
$\displaystyle=\begin{pmatrix}1&&0\\\ \frac{3}{2}kt&&y_{22}\\\
-\frac{3}{2}kt&&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}\frac{3}{2}kt&&y_{22}\\\
-1-\frac{3}{2}kt&&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{Y^{\prime\prime}}$

Either $Y^{\prime\prime}$ has loops, or else by Lemma 2.7 we have that
$Y^{\prime\prime}$ is isomorphic to the Heuberger circulant
$C_{n^{\prime\prime}}(a^{\prime},b^{\prime})$ with
$n^{\prime\prime}=(3kt+1)y_{22}+\frac{9}{2}k^{2}t$ and
$a^{\prime\prime}=\frac{3}{2}kt+1$ and $b^{\prime\prime}=\frac{3}{2}kt$.

» » First suppose $Y^{\prime\prime}$ has loops. Let $M_{Y^{\prime\prime}}$ be
the given matrix for $Y^{\prime\prime}$. By Lemma 2.8 we have that either the
top or bottom row of $M_{Y^{\prime\prime}}$ is zero, or else
$n^{\prime\prime}$ divides every entry in a row of $M_{Y^{\prime\prime}}$. If
the first row is zero, then $kt=0$ and $X$ had loops to begin with, contrary
to assumption. If the second row is zero, then we have $-1-\frac{3}{2}kt=0$
and $y_{22}+3k=0$, so

$\begin{pmatrix}1&&0\\\ \frac{3}{2}kt&&y_{22}\\\
-\frac{3}{2}kt&&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}=\begin{pmatrix}1&&0\\\
-1&&-3k\\\ 1&&0\end{pmatrix}^{\text{SACG}}_{X}\cong\begin{pmatrix}1&&0\\\
1&&3k\\\ 1&&0\end{pmatrix}^{\text{SACG}},$

which is $3$-colorable by Lemma 2.15.

Now suppose that $n^{\prime\prime}$ divides every entry in either the first or
second row of $M_{Y^{\prime\prime}}$. We will work out here the details of the
former case; for the latter, which is similar, see the authors’ notes at [3].
We have that $n^{\prime\prime}\mid\frac{3}{2}kt$ and $n^{\prime\prime}\mid
y_{22}$. Observe that because $X$ does not have loops, hence $t\neq 0$ and
$k\neq 0$ (and therefore $k>0$). We split into cases according to whether $t$
is positive or negative.

First suppose $t>0$. From $n^{\prime\prime}\mid\frac{3}{2}kt$ we get

$\displaystyle-\frac{3}{2}kt\leq(3kt+1)y_{22}+\frac{9}{2}k^{2}t\leq\frac{3}{2}kt$
$\displaystyle\frac{-\frac{3}{2}kt-\frac{9}{2}k^{2}t}{3kt+1}\leq
y_{22}\leq\frac{\frac{3}{2}kt-\frac{9}{2}k^{2}t}{3kt+1}\qquad\text{because
}t>0$
$\displaystyle-\frac{1}{2}-\frac{3}{2}k<y_{22}\leq-\frac{1}{2}-\frac{3}{2}k+\frac{-\frac{1}{2}+\frac{3}{2}k}{3kt+1}<-\frac{3}{2}k$

This cannot happen, because both $k$ and $y_{22}$ are integers.

Now suppose $t<0$. From $n^{\prime\prime}\mid\frac{3}{2}kt$ after some
calculations we get that

$\frac{1}{2}-\frac{3}{2}k>y_{22}\geq-\frac{3}{2}-\frac{3}{2}k.$

Using the fact that $y_{22}$ and $k$ are integers, this tells us that
$y_{22}=-\frac{3}{2}k+\epsilon$ where
$\epsilon\in\\{0,-\frac{1}{2},-1,-\frac{3}{2}\\}$. We will work out here only
the cases where $\epsilon=0$ and $\epsilon=-1$; the other two cases are
similar, and details can be found at [3].

» » » Suppose $\epsilon=0$. Then we have

$\begin{pmatrix}1&0\\\ \frac{3}{2}kt&y_{22}\\\
-\frac{3}{2}kt&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}=\begin{pmatrix}1&0\\\
\frac{3}{2}kt&-\frac{3}{2}k\\\
-\frac{3}{2}kt&\frac{3}{2}k\end{pmatrix}^{\text{SACG}}_{X}=\begin{pmatrix}1&0\\\
0&-\frac{3}{2}k\\\ 0&\frac{3}{2}k\end{pmatrix}^{\text{SACG}}_{X}.$

But this would mean that $X$ has loops, contrary to assumption.

» » » Suppose $\epsilon=-1$. So we must have $y_{22}=-1-\frac{3}{2}k$, which
gives us that $n^{\prime\prime}=-3kt-\frac{3}{2}k-1$. Because
$y_{22}\in\mathbb{Z}$ and $k>0$, it follows that $k$ must be even, so
$y_{22}\leq-4$. From $n^{\prime\prime}\mid y_{22}$, we get that

$-1-\frac{3}{2}k\leq n^{\prime\prime}\leq 1+\frac{3}{2}k,$

which implies that $0\geq t\geq-\frac{5}{3}$ and hence $t=-1$. Recall that

$y_{21}=qy_{22}+\frac{3}{2}k(q-\ell)=qy_{22}+\frac{3}{2}kt=qy_{22}-\frac{3}{2}k=(q+1)y_{22}+1.$

By Def. 2.11, we have that $\frac{y_{22}}{2}=-\frac{|y_{22}|}{2}\leq
y_{21}\leq 0$. Thus we have $y_{22}\leq(2q+2)y_{22}+2\leq 0$. Solving for $q$
and using that $y_{22}\leq-4$, we find that $-\frac{1}{4}\geq q>-1$, which is
a contradiction, since $q$ is an integer.

» » Now suppose that $Y^{\prime\prime}$ does not have loops, so that
$Y^{\prime\prime}$ is isomorphic to the Heuberger circulant
$C_{n^{\prime\prime}}(a^{\prime\prime},b^{\prime\prime})$. We have that
$Y^{\prime\prime}$ (and hence $X$) is $3$-colorable unless one of the six
exceptional cases in Thm. 2.6 occurs. Here we go through only the case where
$b^{\prime\prime}\equiv-2a^{\prime\prime}\;(\textup{mod}\;n^{\prime\prime})$
and $3\nmid n^{\prime\prime}$, and even then, only a few of the illustrative
sub-cases. The others can be found at [3]—as we go along, we will no longer
mention that every time.

The condition
$b^{\prime\prime}\equiv-2a^{\prime\prime}\;(\textup{mod}\;n^{\prime\prime})$
implies that $n^{\prime\prime}\mid\frac{9}{2}kt+2$. We split into cases
according to whether $t$ is positive or negative, and we discuss here only the
case $t<0$. We have

$\frac{9}{2}kt+2\leq(3kt+1)y_{22}+\frac{9}{2}k^{2}t\leq-\frac{9}{2}kt-2.$

After some algebra this leads to

$-\frac{3}{2}k+\frac{3}{2}>y_{22}\geq-\frac{3}{2}k-2.$

Because $3\nmid n^{\prime\prime}=(3kt+1)y_{22}+\frac{9}{2}k^{2}t$, we have
that $3\nmid y_{22}$. Hence, because $k$ and $y_{22}$ are integers, we have
that $y_{22}=-\frac{3}{2}k+\epsilon$ where
$\epsilon\in\\{1,\frac{1}{2},-\frac{1}{2},-1,-2\\}$. We cover here only the
cases $\epsilon=\frac{1}{2}$ and $\epsilon=-\frac{1}{2}$, as they illustrate
some of the various possibilities that can arise.

» » » Suppose $\epsilon=\frac{1}{2}$. It follows that
$n^{\prime\prime}=-\frac{3}{2}k(1-t)+\frac{1}{2}$, from which we find that $k$
is odd and $t$ is even. From $n^{\prime\prime}\mid\frac{9}{2}kt+2$ we get that
$n^{\prime\prime}\mid\frac{9}{2}k+\frac{1}{2}$ gives us that
$n^{\prime\prime}=\pm 1$. Thus

$\frac{9}{2}k+\frac{1}{2}\leq-\frac{3}{2}k(1-t)+\frac{1}{2}.$

Solving for $t$, we find that

$-4-\frac{2}{3k}\leq t,$

which gives us that $t=-2$ or $t=-4$. If $t=-2$, then
$n^{\prime\prime}=-\frac{9}{2}k+\frac{1}{2}\leq-4$, which together with
$n^{\prime\prime}\mid\frac{9}{2}k+\frac{1}{2}$ gives us that
$n^{\prime\prime}\mid 1$, a contradiction. So $t=-4$. Then
$n^{\prime\prime}=-\frac{15}{2}k+\frac{1}{2}\leq-7$. Thus $n^{\prime\prime}$
divides $5(\frac{9}{2}k+\frac{1}{2})+3n^{\prime\prime}=4$, a contradiction.

» » » Suppose $\epsilon=-\frac{1}{2}$. It follows that
$n^{\prime\prime}=-\frac{3}{2}k(1+t)-\frac{1}{2}$. Thus $k$ is odd and $t$ is
even. Using the same sort of logic as in the $\epsilon=\frac{1}{2}$ case, we
get that $n^{\prime\prime}\mid-\frac{9}{2}k+\frac{1}{2}$, and we again find
that $t=-2$ or $t=-4$. If $t=-2$, we have
$n^{\prime\prime}=\frac{3}{2}k-\frac{1}{2}>0$. So $n^{\prime\prime}$ divides
$-\frac{9}{2}k+\frac{1}{2}+3n^{\prime\prime}=-1$, giving us
$n^{\prime\prime}=1$, in turn giving us $k=1$. But then
$y_{22}=-\frac{3}{2}k+\epsilon=-2$ and $y_{32}=y_{22}+3k=1$, violating the
condition $|y_{22}|\leq|y_{32}|$ from Def. 2.11.

So $t=-4$. This gives us that $n^{\prime\prime}=\frac{9}{2}k-\frac{1}{2}\geq
4$. By the choice of $\epsilon$, we have
$y_{22}=-\frac{3}{2}k-\frac{1}{2}\leq-2$. By Def. 2.11 and our previous
formula for $y_{21}$, we have that

$-\frac{3}{4}k-\frac{1}{4}\leq
q\left(-\frac{3}{2}k-\frac{1}{2}\right)+\frac{3}{2}k(-4)\leq 0.$ (4)

Solving for $q$, we find that

$-5\geq-7+\frac{8}{3k+1}\geq 2q\geq-8.$ (5)

Because $q$ is an integer, this gives us that $q=-3$ or $q=-4$. If $q=-3$,
then from (5) and from the fact that $k$ is an odd positive integer, we get
that $k=1$. But then $y_{22}=-\frac{3}{2}k+\epsilon=-2$ and
$y_{32}=y_{22}+3k=1$, violating the condition $|y_{22}|\leq|y_{32}|$ from Def.
2.11. So $q=-4$. But this contradicts (4).

» Now suppose that $Y^{\prime}$ does not have loops, so $Y^{\prime}$ is
isomorphic to the Heuberger circulant $C_{n^{\prime}}(a^{\prime},b^{\prime})$
with $n^{\prime}=2y_{22}+3k$ and $a^{\prime}=-2y_{21}-3k\ell$ and
$b^{\prime}=1$. We have that $Y^{\prime}$ (and hence $X$) is $3$-colorable
unless one of the six exceptional cases in Thm. 2.6 occurs. We work out here
with some granularity only one of these cases, namely where $3\nmid
n^{\prime}$ and $a^{\prime}\equiv 2b^{\prime}\;(\textup{mod}\;n^{\prime})$.
The other five cases are handled similarly. Complete details can be found in
our authors’ notes, which are housed on the second author’s website [3].

From $3\nmid n^{\prime}$ we get that $3\nmid y_{22}$. From $a^{\prime}\equiv
2b^{\prime}\;(\textup{mod}\;n^{\prime})$ we get that
$y_{21}=qy_{22}-1+\frac{3}{2}k(q-\ell)$ for some integer $q$. Let $t=q-\ell$.
Note $k$ or $t$ must be even. We have:

$\begin{pmatrix}1&0\\\ y_{21}&y_{22}\\\
y_{21}+3k\ell&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}=\begin{pmatrix}1&0\\\
qy_{22}-1+\frac{3}{2}k(q-\ell)&y_{22}\\\
qy_{22}-1+\frac{3}{2}k(q-\ell)+3k\ell&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}$

$=\begin{pmatrix}1&0\\\ qy_{22}-1+\frac{3}{2}k(q-\ell)&y_{22}\\\
qy_{22}-1+\frac{3}{2}k(q+\ell)&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}=\begin{pmatrix}1&0\\\
-1+\frac{3}{2}k(q-\ell)&y_{22}\\\
-1+\frac{3}{2}k(-q+\ell)&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}=\begin{pmatrix}1&0\\\
-1+\frac{3}{2}kt&y_{22}\\\
-1-\frac{3}{2}kt&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}$

Suppose $t=0$. Then $y_{21}=qy_{22}-1$. From Def. 2.11 we have that
$-\frac{|y_{22}|}{2}\leq y_{21}\leq 0$. Suppose $y_{22}>0$. If $y_{22}=1$,
then $y_{21}=0$, and in this case the theorem now follows from Lemma 2.17. So
we may assume that $y_{22}\geq 2$. Then from $qy_{22}-1\leq 0$ we get that
$q\leq 0$. From $-\frac{y_{22}}{2}\leq qy_{22}-1$ we then get that $q=0$. From
$t=q-\ell$ we then get $\ell=0$. So $y_{21}=y_{31}=-1$. After multiplying the
bottom row of $M_{X}$ by $-1$, the theorem now holds by Lemma 2.15. The same
is true for similar reasons if $y_{22}<0$. Hence we may assume that $t\neq 0$.
A similar argument shows that we may assume that $k\neq 0$.

We divide now into cases according to whether $t>0$ or $t<0$. We write here
only about the case $t<0$, the case $t>0$ being similar.

Consider the mapping

$\begin{pmatrix}1&0\\\ -1+\frac{3}{2}kt&y_{22}\\\
-1-\frac{3}{2}kt&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{X}\xrightarrow{\ocirc}\begin{pmatrix}\frac{3}{2}kt&y_{22}\\\
-1-\frac{3}{2}kt&y_{22}+3k\end{pmatrix}^{\text{SACG}}_{Y^{\prime\prime}}$

Either $Y^{\prime\prime}$ has loops, or else by Lemma 2.7 we have that
$Y^{\prime\prime}\cong
C_{n^{\prime\prime}}(a^{\prime\prime},b^{\prime\prime})$ where
$a^{\prime\prime}=1+\frac{3}{2}kt$ and $b^{\prime\prime}=\frac{3}{2}kt$ and
$n^{\prime\prime}=(3kt+1)y_{22}+\frac{9}{2}k^{2}t$. Let $M_{Y^{\prime\prime}}$
be the Heuberger matrix for $Y^{\prime\prime}$ given above. Because $kt\neq 0$
and $kt\in\mathbb{Z}$, it follows that neither row of $M_{Y^{\prime\prime}}$
is a zero row. Lemma 2.8 then tells us that $Y^{\prime\prime}$ has loops if
and only if $n^{\prime\prime}$ divides every entry in either the top or bottom
row of $M_{Y^{\prime\prime}}$. Otherwise, we have that $Y^{\prime\prime}$ (and
hence $X$) is $3$-colorable unless one of the six exceptional cases in Theorem
2.6 holds. This gives us a total of eight cases to consider. Of those, we
write here only about the possibility that $n^{\prime\prime}$ divides both
$-1-\frac{3}{2}kt$ and $y_{22}+3k$. The other seven cases can be managed using
the same sort of techniques we’ve employed throughout this subsection; a full
exposition can be found in [3].

To recap, we now assume that $n^{\prime\prime}\mid-1-\frac{3}{2}kt$ and
$n^{\prime\prime}\mid y_{22}+3k$ and $t<0$ and $k>0$. So

$1+\frac{3}{2}kt\leq(3kt+1)y_{22}+\frac{9}{2}k^{2}t\leq-1-\frac{3}{2}kt.$

Solving for $y_{22}$ we find that

$\frac{1}{2}-\frac{3}{2}k>y_{22}\geq-1-\frac{3}{2}k.$

Because $k,y_{22}\in\mathbb{Z}$, we have that $y_{22}=-\frac{3}{2}k+\epsilon$
where $\epsilon\in\\{-1,-\frac{1}{2},0\\}$. We write here only about the case
where $\epsilon=-1$. The cases where $\epsilon=-\frac{1}{2}$ or $\epsilon=0$
use the same sorts of techniques we’ve seen previously. So assume
$y_{22}=-\frac{3}{2}k-1$. Then $n^{\prime\prime}=-3k(\frac{1}{2}+t)-1$ and
$y_{22}+3k=\frac{3}{2}k-1>0$. So from $n^{\prime\prime}\mid y_{22}+3k$ we have
that

$-3k\left(\frac{1}{2}+t\right)-1\leq\frac{3}{2}k-1.$

Solving for $t$, we find that $t\leq-1$. Because $t$ is a negative integer,
this implies that $t=-1$. Recall that
$y_{21}=qy_{22}-1+\frac{3}{2}kt=(q+1)y_{22}$. By Def. 2.11 we have that
$\frac{y_{22}}{2}\leq y_{21}=(q+1)y_{22}\leq 0$. Here we use that $y_{22}<0$.
Dividing by $y_{22}$ we get that $\frac{1}{2}\geq q+1\geq 0$, so $q=-1$,
because $q$ is an integer. Then $y_{21}=0$. From $t=q-\ell$ we get $\ell=0$,
so $y_{21}=0$. But then $X$ had loops, contrary to assumption.∎

The operations performed to put a $3\times 2$ matrix $M$ into modified Hermite
normal form do not affect the gcd of the determinants of the $2\times 2$
minors of $M$. Hence we have the following corollary to Theorem 2.14, in
analogy to Corollary 2.10.

######  Corollary 2.18.

Suppose $X$ is a standardized abelian Cayley graph with an associated $3\times
2$ Heuberger matrix $M_{X}$. If $X$ does not have loops, and if $3$ divides
the determinant of every $2\times 2$ minor of $M_{X}$, then $X$ is
$3$-colorable.

###### Proof.

If $M_{X}$ has a zero row, we may delete it without affecting the chromatic
number, so in this case, the result follows from Cor. 2.10. If the columns of
$M_{X}$ are linearly dependent over $\mathbb{Q}$, then after appropriate
column operations we obtain a zero column, whereupon the result follows from
[1, Thm. LABEL:general-theorem-tree-guard]. Otherwise, as noted just before
the statement of this corollary, we may assume that $M_{X}$ is in modified
Hermite normal form. But for each of the six types of matrices $M_{X}$ in the
third statement in Theorem 2.14 for which $\chi(X)>3$, at least one $2\times
2$ minor has a determinant not divisible by $3$. The result follows.∎

It would be interesting to know whether Cor. 2.18 holds for matrices of
arbitrary size. We conjecture that it does.

Indeed, we remark that Thm. 2.14 can be recast entirely so that one can
determine the chromatic number directly from an arbitrary Heuberger matrix
$M$, not necessarily in modified Hermite normal form. Namely, let
$\alpha,\beta,\gamma$ be the absolute values of the determinants of the
$2\times 2$ minors of $M$, such that $\alpha\leq\beta\leq\gamma$. The six
exceptional cases in Thm. 2.14 occur precisely when (i) one row of $M$ has
relatively prime entries, and (ii) $\alpha>0$, and (iii) either
$\\{\alpha,\beta,\gamma\\}=\\{1,2,3k\\}$ for some positive integer $k$, or
else $\gamma=\alpha+\beta$ and $\alpha\not\equiv\beta\;(\textup{mod}\;3)$. The
other cases (bipartite, loops, zero row, etc.) can easily be characterized
directly from $M$.

We previously noted that for a standardized abelian Cayley graph $X$ with an
associated $2\times 2$ Heuberger matrix $M_{X}$:

(*) If $X$ does not have loops, then $X$ fails to be $4$-colorable if and only
if it contains $K_{5}$ as a subgraph, and it fails to be $3$-colorable if and
only if it contains either $C_{13}(1,5)$ or a diamond lanyard as a subgraph.

Consequently, (*) holds for a $3\times 2$ matrix with a zero row, as the
corresponding graph equals a box product of a doubly infinite path graph and a
graph with a $2\times 2$ matrix. Each of the six exceptional cases in the
third statement in Theorem 2.14 contains a diamond lanyard as a subgraph, as
we saw in the proofs of Lemmas 2.15, 2.16, and 2.17. Thus (*) holds also for
every standardized abelian Cayley graph $X$ with an associated $3\times 2$
Heuberger matrix $M_{X}$.

###  2.6 An algorithm to find the chromatic number for $1\times r,m\times
1,2\times r$, or $3\times 2$ matrices

In this subsection, we provide a “quick-reference guide” to the results of
this section. Specifically, we spell out a procedure to determine the
chromatic number of a standardized abelian Cayley graph with a Heuberger
matrix $M_{X}$ of size $1\times r,m\times 1,2\times r$, or $3\times 2$, where
$m$ and $r$ are positive integers. This procedure can easily be converted into
code or pseudocode. Indeed, an implementation of this algorithm in Mathematica
can be found at [3].

$\bullet$ If $M_{X}$ is of size $m\times 1$, apply [1, Theorem LABEL:general-
theorem-tree-guard].

$\bullet$ If $M_{X}$ is of size $1\times r$, apply Lemma 2.1.

$\bullet$ If $M_{X}$ is of size $2\times 2$, apply column operations as per
[1, Lemma LABEL:general-lemma-isomorphisms] to produce a lower-triangular
matrix. Then apply Theorem 2.9; if the last statement in that theorem holds,
use Theorem 2.6 to complete the final step in the computation.

$\bullet$ If $M_{X}$ is of size $2\times r$ for $r>2$, perform column
operations as per [1, Lemma LABEL:general-lemma-isomorphisms] to produce a
zero column. Delete that column, and iterate this procedure until you have a
$2\times 2$ matrix. Then use the procedure from the previous bullet point.

$\bullet$ If $M_{X}$ is of size $3\times 2$, do the following. If $M_{X}$ has
a zero row, delete that row, then use the procedure for $2\times 2$ matrices
to find the chromatic number of the graph with the resulting matrix. If the
columns of $M_{X}$ are linearly dependent over $\mathbb{Q}$, perform column
operations as per [1, Lemma LABEL:general-lemma-isomorphisms] to produce a
zero column. Delete that column, and then apply [1, Theorem LABEL:general-
theorem-tree-guard]. Otherwise, use row and column operations as per Lemma
2.12 to find an isomorphic graph $X^{\prime}$ with a Heuberger matrix
$M_{X^{\prime}}$ in modified Hermite normal form. Then apply Theorem 2.14.

## Acknowledgments

The authors wish to thank Tim Harris for his careful read of an early version
of this manuscript and for his many helpful suggestions.

## References

  * [1] J. Cervantes and M. Krebs, _Chromatic numbers of Cayley graphs of abelian groups: A matrix method_ , www.arxiv.org.
  * [2] , _A generalization of Zhu’s theorem on six-valent integer distance graphs_ , www.arxiv.org.
  * [3] Cervantes, J. and Krebs, M., _Authors’ notes: Chromatic number of $\mathbb{Z}^{n}$ mod rank two subgroup_, https://www.calstatela.edu/research/mkrebs.
  * [4] Clemens Heuberger, _On planarity and colorability of circulant graphs_ , Discrete Mathematics 268 (2003), no. 1, 153–169.
  * [5] MathOverflow, _Chromatic numbers of infinite abelian Cayley graphs_ , https://mathoverflow.net/questions/304715/chromatic-numbers-of-infinite-abelian-cayley-graphs, accessed Apr. 5, 2021.
  * [6] J. Pommersheim, T. Marks, and E. Flapan, _Number theory: A lively introduction with proofs, applications, and stories_ , Wiley, Hoboken, New Jersey, 2010.
  * [7] Alexander Soifer, _The mathematical coloring book_ , Springer, New York, 2009, Mathematics of coloring and the colorful life of its creators, With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau.
  * [8] Xuding Zhu, _Circular chromatic number of distance graphs with distance sets of cardinality 3_ , J. Graph Theory 41 (2002), no. 3, 195–207.