Colorings instance:undirected G(V,E)with max-degree <A q colors: goal:counting the number of proper g-colorings for G exact counting is #P-hard ·when g<△，decision of existence is NP-hard approximately counting the number of proper q-colorings for G when g≥△+β equivalent to sampling an almost uniform random q-coloringColorings instance: undirected G(V,E) with max-degree ≤Δ goal: counting the number of proper q-colorings for G q colors: • exact counting is #P-hard • when q<Δ , decision of existence is NP-hard approximately counting the number of proper q-colorings for G when q ≥αΔ+β equivalent to sampling an almost uniform random q-coloring