An FPTAS for Counting Proper Four-Colorings on Cubic Graphs

Pinyan Lu, Kuan Yang, Chihao Zhang +1

Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting. It is conjectured that there is a fully polynomial-time (randomized) approxima…