Markoy Random Fields (MRF) Gibbs distribution u:Voe[g] network GE): H(o)Ae(ou,)b(o) e=(u,w)∈E ●proper q-coloring: X∈[q] ⑨bv 10 1 independent set: 4-且司-日 X∈[aly follows u local conflict colorings: [Fraigniaud,Heinrich,Kosowski FOCS'16] Ae∈{0,1}9×9，bm∈{0,1}9Markov Random Fields network G(V,E): Ae bv Xv∈[q] u v X ~ 2 [q] V follows µ (MRF) • Gibbs distribution µ : ∀σ∈[q]V µ(￾) / Y e=(u,v)2E Ae(￾u, ￾v) Y v2V bv(￾v) • proper q-coloring: Ae = 2 6 6 6 4 0 0 ... 0 3 7 7 7 5 1 1 bv = 2 6 4 1 . . . 1 3 7 5 • independent set: bv =  1 1 ￾ Ae =  1 1 1 0￾ • local conflict colorings: [Fraigniaud, Heinrich, Kosowski FOCS’16] Ae 2 {0, 1}q⇥q, bv 2 {0, 1}q