Chromatic numbers of Cayley graphs of abelian groups: A matrix method
Linear Algebra and its Applications · 2023-11 · 676 · 277-295
DOI: 10.1016/j.laa.2023.07.016 ↗Kurz gefasst
Fachartikel in der Zeitschrift Linear Algebra and its Applications, 2023-11. Verfasst von Jonathan Cervantes und 1 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).
Abstract (Originalsprache)
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\times 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.
Zitieren
APA
Cervantes, J., & Krebs, M. (2023). Chromatic numbers of Cayley graphs of abelian groups: A matrix method. Linear Algebra and its Applications, 676, 277-295. https://doi.org/10.1016/j.laa.2023.07.016
Vancouver
Cervantes J, Krebs M. Chromatic numbers of Cayley graphs of abelian groups: A matrix method. Linear Algebra and its Applications. 2023;676:277-295. doi:10.1016/j.laa.2023.07.016
BibTeX
@article{Cervantes2023,
author = {Cervantes, Jonathan and Krebs, Mike},
title = {Chromatic numbers of Cayley graphs of abelian groups: A matrix method},
journal = {Linear Algebra and its Applications},
year = {2023},
volume = {676},
pages = {277--295},
doi = {10.1016/j.laa.2023.07.016}
}
EUVIMED