LocalMetropolis for q-Coloring starting from an arbitrary X∈[g]',at each step,each vertex ve∈： proposes a color ovE[g]uniformly and independently at random; accepts the proposal and update Xy to o,if for all v's neighbors u: X≠0vAOu≠XNOu≠0v; q≥(2+V2+e)A> Tmix=O(log n) The mixing time holds even for unbounded A and g. ●q2(l+s)△：each vertex is updated at(l)rate in LocalMetropolisLocalMetropolis for q-Coloring starting from an arbitrary X ∈ [q]V , at each step, each vertex v∈V: proposes a color σv∈[q] uniformly and independently at random; accepts the proposal and update Xv to σv if for all v’s neighbors u: Xu≠σv ∧ σu≠Xv ∧ σu≠σv ; q ￾ (2 + τmix=O(log n) p 2 + ✏)￾ • The mixing time holds even for unbounded Δ and q. • q≥(1+ε)Δ: each vertex is updated at Ω(1) rate in LocalMetropolis