The problem of coloring random graphs is a well-known problem in computer science that has received ample attention. The problem consists of finding an assignment of colors--from a predefined set--for all vertices of a graph, such that no adjacent vertices get the same color. There has been progress in solving this problem--a well-known conjecture is that four colors are enough for planar graphs. However, for the case of arbitrarily large graphs, not much is currently known. This is where Dyer and Frieze’s paper makes a contribution, by considering the discrete Markov chain implemented in Glauber dynamics.

The paper consists mainly of the proof of a new theorem that is stated right after the introduction. The proof consists of coupling two Glauber stochastic processes. A nice property is that these chains tend to meet rapidly for an arbitrary initial coloring.

The paper is highly technical. A good background in graph theory and stochastic processes--Markov chains and Glauber dynamics--is required to fully understand the main ideas. However, those who are not interested in the minute details involved in the proofs will find the main result rather easy to understand and follow.