  We address the problem of sampling colorings of a graph $G$ by Markov chain
simulation. For most of the article we restrict attention to proper
$q$-colorings of a path on $n$ vertices (in statistical physics terms, the
one-dimensional $q$-state Potts model at zero temperature), though in later
sections we widen our scope to general ``$H$-colorings'' of arbitrary graphs
$G$. Existing theoretical analyses of the mixing time of such simulations
relate mainly to a dynamics in which a random vertex is selected for updating
at each step. However, experimental work is often carried out using systematic
strategies that cycle through coordinates in a deterministic manner, a dynamics
sometimes known as systematic scan. The mixing time of systematic scan seems
more difficult to analyze than that of random updates, and little is currently
known. In this article we go some way toward correcting this imbalance. By
adapting a variety of techniques, we derive upper and lower bounds (often
tight) on the mixing time of systematic scan. An unusual feature of systematic
scan as far as the analysis is concerned is that it fails to be time
reversible.
