More precisely, the random walk proceeds by repeatedly choosing a uniformly random vertex and choosing uniformly at random among all the available colors for that vertex, including the color it already had; this process is called the Glauber dynamics.