Counting independent sets and colorings on random regular bipartite graphs

Chao Liao, Jiabao Lin, Pinyan Lu +1

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every $\Delta$-regular bipartite graph if $\Delta \ge 53$. In the weighted case,…