Algorithms to Approximately Count and Sample Conforming Colorings of Graphs

Conforming colorings naturally generalize many graph theory structures, including independent sets, vertex colorings, list colorings, H-colorings and adapted colorings. Given a multigraph G and a function F that assigns a forbidden ordered pair of colors to each edge e, we say a coloring C of the vertices is conforming to F if, for all e=(u,v),F(e)≠(C(u),C(v)). We consider Markov chains on the set of conforming colorings and provide some general conditions for when they can be used to construct efficient Monte Carlo algorithms for sampling and counting.