NP-hardness for Bipartite Colorings up to the Maximum DegreeResearch Paper
Counting the proper -colorings of a graph of maximum degree is the central test case of approximate counting. Since Jerrum (1995) it has been conjectured that an FPRAS exists for general graphs whenever , and the rapid-mixing bounds for Glauber dynamics have moved from toward that threshold. On the hardness side, Galanis,…