△-regular tree each v: proposes a uniform random color o,[q]; update X to if for all v's neighbors u: X≠GvAO计XAG≠0v; Xroot red,Yroot blue V non-root v,Xy=Yy fred,blue} coupling:coupling the proposals (so that (( vertex v proposes consistently:= red if oy=blue vertex v proposes bijectively:o= blue if oy=red otherwise I.the root proposes consistently; 2.each child of the root proposes bijectively; 3. each vertex of depth >2 proposes bijectively if its parent proposed different colors in the two chains,and proposes consistently if otherwise;Xroot = red , Yroot = blue Δ-regular tree ∀ non-root v, Xv = Yv ∉ {red, blue} proposes a uniform random color σv∈[q]; update Xv to σv if for all v’s neighbors u: Xu≠σv ∧ σu≠Xv ∧ σu≠σv ; each v: coupling: coupling the proposals (σX , σY) so that (X, Y ) (￾ X ,￾ Y ) ￾! (X0 , Y 0 ) 1. the root proposes consistently; 2. each child of the root proposes bijectively; 3. each vertex of depth ≥2 proposes bijectively if its parent proposed different colors in the two chains, and proposes consistently if otherwise; vertex v proposes consistently: ￾X v = ￾Y v vertex v proposes bijectively: ￾X v = 8 >< >: red if ￾Y v = blue blue if ￾Y v = red ￾Y v otherwise