  We introduce a new notion of error-correcting codes on $[q]^n$ where a code
is a set of proper $q$-colorings of some fixed $n$-vertex graph $G$. For a pair
of proper $q$-colorings $X, Y$ of $G$, we define their distance as the minimum
Hamming distance between $X$ and $\sigma(Y)$ over all $\sigma \in S_q$. We then
say that a set of proper $q$-colorings of $G$ is $\delta$-distinct if any pair
of colorings in the set have distance at least $\delta n$.
  We investigate how one-sided spectral expansion relates to the largest
possible set of $\delta$-distinct colorings on a graph. For fixed $(\delta,
\lambda) \in [0, 1] \times [-1, 1]$ and positive integer $d$, let $f_{\delta,
\lambda, d}(n)$ denote the maximal size of a set of $\delta$-distinct colorings
of any $d$-regular graph on at most $n$ vertices with normalized second
eigenvalue at most $\lambda$. We study the growth of $f$ as $n$ goes to
infinity. We partially characterize regimes of $(\delta, \lambda)$ where $f$
grows exponentially, is finite, and is at most $1$, respectively. We also prove
several sharp phase transitions between these regimes.
