On the chromatic number of structured Cayley graphs

Mohammad Bardestani, Keivan Mallahi-Karai

Published 2015-11-08Version 1

In this note, we will study the chromatic number of Cayley graphs of algebraic groups that arise from algebraic constructions. Using Lang-Weil bound and Gowers' mixing inequality for quasirandom groups, we will establish lower bounds on the chromatic number of these graphs. This provides a lower bound for the chromatic number of Cayley graphs of the regular graphs associated to the ring of $n\times n$ matrices over finite fields. Using Weil's bound for Kloosterman sums we will also prove an analogous result for $\mathrm{SL}_2$ over finite rings.