Chromatic numbers of abelian Cayley graphs (Michael Krebs, Cal State LA)

A classic problem in graph theory is to find the chromatic number of a given graph: that is, to find the smallest number of colors needed to assign every vertex a color such that whenever two vertices are adjacent, they receive different colors.  This problem has been studied for many families of graphs, including cube-like graphs, unit-distance graphs, circulant graphs, integer distance graphs, Paley graphs, unit-quadrance graphs, etc.  All of those examples just listed can be regarded as “abelian Cayley graphs,” that is, Cayley graphs whose underlying group is abelian.  Our goal is to create a unified, systematic approach for dealing with problems of this sort, rather than attacking each individually with ad hoc methods.  Building upon the work of Heuberger, we associate an integer matrix to each abelian Cayley graph.  In certain cases, such as when the matrix is small enough, we can more or less read the chromatic number directly from the entries of the matrix.  In this way we immediately recover both Payan’s theorem (that cubelike graphs cannot have chromatic number 4) as well as Zhu’s theorem (which determines the chromatic number of six-valent integer distance graphs).  The proofs utilize only elementary group theory, elementary graph theory, elementary number theory, and elementary linear algebra.  This is joint work with J. Cervantes.