Colorings instance:undirected G(V,E)with max-degree <A g colors: g a goal:counting the number of proper g-colorings for G exact counting is #P-hard 。when g<△，decision of existence is NP-hardColorings 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