First Passage Percolation for Random Colorings of Zd

Random colorings (independent or dependent) of Zd give rise to dependent first-passage percolation in which the passage time along a path is the number of color changes. Under certain conditions, we prove strict positivity of the time constant (and a corresponding asymptotic shape result) by means of a theorem of Cox, Gandolfi, Griffin and Kesten about "greedy" lattice animals. Of particular interest are i.i.d. colorings and the d=2 Ising model. We also apply the greedy lattice animal theorem to prove a result on the omnipresence of the infinite cluster in high density independent bond percolation.