  In this paper, we will study the chromatic number of Cayley graphs of
algebraic groups that arise from algebraic constructions. Using Lang-Weil bound
and representation theory of finite simple groups of Lie type, 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.
