\indent Given a fixed graph $G$ on $n$ vertices, we can create a random coloring of $G$ in the following way: randomly pick an edge, then randomly pick a color, and then color both endpoints of that edge that color. We can continue this process on a graph that is already colored by simply overwriting any vertices that have already been assigned a color. This gives rise to a random walk on the $2^n$ colorings of $G$, and it is this random walk that we will investigate. The eigenvalues of the transition matrix are known and have a simple form. We discuss these and other quantities as well as several related problems.