  An $n$-lift of a graph $G$ is a graph from which there is an $n$-to-$1$
covering map onto $G$. Amit, Linial, and Matou\v sek (2002) raised the question
of whether the chromatic number of a random $n$-lift of $K_5$ is concentrated
on a single value. We consider this problem for $G=K_{d+1}$, and show that for
fixed $d\ge 3$ the chromatic number of a random lift of $K_d$ is
(asymptotically almost surely) either $k$ or $k+1$, where $k$ is the smallest
integer satisfying $d < 2k \log k$. Moreover, we show that, for roughly half of
the values of $d$, the chromatic number is concentrated on $k$. The argument
for the upper-bound on the chromatic number uses the small subgraph
conditioning method, and it can be extended to random $n$-lifts of $G$, for any
fixed $d$-regular graph $G$.
