Coloring percolation clusters at random

We consider the random coloring of the vertices of a graph G, that arises b y first performing i.i.d. bond percolation with parameter p on G, and then assigning a random color, chosen according to some prescribed probability d istribution on the finite set {0,..., r-1}, to each of the connected compon ents, independently for different components. We call this the divide and c olor model, and study its percolation and Gibbs (quasilocality) properties, with emphasis on the case G = Z(d). On Z(2), having an infinite cluster in the underlying bond percolation process turns out to be necessary and suff icient for some single color to percolate; this fails in higher k-dimension s. Gibbsianness of the coloring process on Z(d), d greater than or equal to 2, holds when p is sufficiently small, but not when p is sufficiently larg e. For r = 2, an FKG inequality is also obtained. (C) 2001 Elsevier Science B.V. All rights reserved.