Algorithms to approximately count and sample conforming colorings of graphs

Given a multigraph  GG and a function  FF that assigns a forbidden ordered pair of colors to each edge ee, we say a coloring  CC of the vertices is conforming to     FF if for all e=(u,v)e=(u,v), (C(u),C(v))≠F(e)(C(u),C(v))≠F(e). Conforming colorings generalize many natural graph theoretic concepts, including independent sets, vertex colorings, list colorings, HH-colorings and adapted colorings and consequently there are known complexity barriers to sampling and counting. We introduce natural Markov chains on the set of conforming colorings and provide general conditions for when they can be used to design efficient Monte Carlo algorithms for sampling and approximate counting.