Chromatic numbers of Cayley graphs of abelian groups: a matrix method

DOI10.1016/J.LAA.2023.07.016MaRDI QIDQ6178783zbMATH OpenOpenAlexFDO

Authors J. Cervantes, Mike Krebs

Publication date 5 September 2023

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2303.06262

zbMATH Keywords

abelian group Cayley graph chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: In this paper, we take a modest first step towards a systematic study of chromatic numbers of Cayley graphs on abelian groups. We lose little when we consider these graphs only when they are connected and of finite degree. As in the work of Heuberger and others, in such cases the graph can be represented by an

m i m e s r

integer matrix, where we call

m

the dimension and

r

the rank. Adding or subtracting rows produces a graph homomorphism to a graph with a matrix of smaller dimension, thereby giving an upper bound on the chromatic number of the original graph. In this article we develop the foundations of this method. In a series of follow-up articles using this method, we completely determine the chromatic number in cases with small dimension and rank; prove a generalization of Zhu's theorem on the chromatic number of

6

-valent integer distance graphs; and provide an alternate proof of Payan's theorem that a cube-like graph cannot have chromatic number 3.

Review text

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\).

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Chromatic numbers of Cayley graphs of abelian groups: a matrix method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6178783)