EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

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

Jonathan Cervantes, Mike Krebs

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →