Chromatic numbers of Cayley graphs of abelian groups: a matrix method (Q6178783)

The chromatic number \(\chi(X)\) of a (finite or infinite) graph \(X\) is the least number of colours required to colour its vertices such that adjacent vertices receive different colours. For a group \(G\), finite or infinite, and an inverse-closed subset \(S\) of \(G\), the Cayley graph on \(G\) with connection set \(S\), written \(\mathrm{Cay}(G, S)\), is the graph with vertex set \(G\) such that \(x\), \(y\) are adjacent if and only if \(x^{-1} y \in S\). Since \(S\) is inverse-closed, this graph is undirected, and it is connected if and only if \(S\) generates \(G\). (The authors allow the identity element of \(G\) to be contained in \(S\); in this case \(\mathrm{Cay}(G, S)\) has a loop at each vertex.) The problem of determining the chromatic number of a Cayley graph has been studied in many special cases, but there is a lack of systematic approaches to the problem even when the group involved is abelian. In this paper and a series of follow-up papers, the authors propose a systematic unified approach to this problem for Cayley graphs on abelian groups. In the reviewer's opinion, this approach is essentially about homomorphisms among abelian Cayley graphs through operations of their Heuberger matrices. More explicitly, following [\textit{C. Heuberger}, Discrete Math. 268, No. 1--3, 153--169 (2003; Zbl 1028.05024)], any abelian Cayley graph \(\mathrm{Cay}(G, S)\) is isomorphic to a standardized abelian Cayley graph \(X = \mathrm{Cay}(\mathbb{Z}^m/H, \{H+e_1, \ldots, H+e_m\})\), where \(G\) is an abelian group with operation written additively, \(S = \{\pm g_1, \ldots, \pm g_m\}\) is an inverse-closed subset of \(G\), \(e_i\) is the element of \(\mathbb{Z}^m\) with \(1\) at the \(i\)-th coordinate and \(0\) at all other coordinates, and \(H\) is the kernel of the homomorphism from \(\mathbb{Z}^m\) to \(G\) which maps \(g_i\) to \(e_i\) for each \(i\). Since \(H\) is a subgroup of \(\mathbb{Z}^m\), it is generated by, say, \(y_1, \ldots, y_r \in \mathbb{Z}^m\), and the \(m \times r\) integer matrix \(M_X\) with columns \(y_1, \ldots, y_r\), called a Heuberger matrix of \(X\), contains all information about the adjacency relation of \(X \cong \mathrm{Cay}(G, S)\). It is anticipated that one may study chromatic numbers of abelian Cayley graphs by means of their Heuberger matrices. In the paper, the authors explain this approach in detail and prove several basic results about it, including how one can obtain graph homomorphisms from certain row or column operations of Heuberger matrices. Using their approach, the authors give a new proof of Payan's theorem, which says that no cube-like graph can have chromatic number 3, where a cube-like graph is a Cayley graph on an elementary abelian \(2\)-group. Another interesting result obtained via their approach is that for any algebraic integer \(\omega \in \mathbb{C}\), if the Cayley graph on \(\mathbb{C}\) with connection set \(\{\omega^i: i \ge 0\}\) has chromatic number no less than \(4\), then the minimal polynomial of \(\omega\) over the integers must have unit modulus when evaluated at \(1\) or \(-1\).