We prove that every (possibly infinite) graph of degree at most d has a 4-dependent random proper 4d(d+1)/2-coloring, and one can construct it as a finitary factor of iid. For unimodular transitive (or unimodular random) graphs we construct an automorphism-invariant (respectively, unimodular) 2-dependent coloring by 3d(d+1)/2 colors. In particular, there exist random proper colorings for ᵈ and for the regular tree that are 2-dependent and automorphism-invariant, or 4-dependent and finitary factor of iid.
No takes yet. Share an insight, caveat, or question.
Ádám Timár (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: