  A proper $q$-coloring of a domain in $\mathbb{Z}^d$ is a function assigning
one of $q$ colors to each vertex of the domain such that adjacent vertices are
colored differently. Sampling a proper $q$-coloring uniformly at random, does
the coloring typically exhibit long-range order? It has been known since the
work of Dobrushin that no such ordering can arise when $q$ is large compared
with $d$. We prove here that long-range order does arise for each $q$ when $d$
is sufficiently high, and further characterize all periodic maximal-entropy
Gibbs states for the model. Ordering is also shown to emerge in low dimensions
if the lattice $\mathbb{Z}^d$ is replaced by
$\mathbb{Z}^{d_1}\times\mathbb{T}^{d_2}$ with $d_1\ge 2$, $d=d_1+d_2$
sufficiently high and $\mathbb{T}$ a cycle of even length. The results address
questions going back to Berker--Kadanoff (1980), Koteck\'y (1985) and
Salas--Sokal (1997).
