An FPTAS for counting proper four-colorings on cubic graphs

DOI10.1137/1.9781611974782.117zbMATH Open1410.05207arXiv1611.04100OpenAlexW2950027515MaRDI QIDQ4575863FDOQ4575863

Authors: Pinyan Lu, Kuan Yang, Chihao Zhang, Minshen Zhu 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: 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) approximation scheme (FPTAS/FPRAS) for counting the number of proper colorings as long as $qgeqDelta+1$, where $q$ is the number of colors and $Delta$ is the maximum degree of the graph. The bound of $q=Delta+1$ is the uniqueness threshold for Gibbs measure on $Delta$-regular infinite trees. However, the conjecture remained open even for any fixed $Deltageq3$ (The cases of $Delta=1,2$ are trivial). In this paper, we design an FPTAS for counting the number of proper $4$-colorings on graphs with maximum degree $3$ and thus confirm the conjecture in the case of $Delta=3$. This is the first time to achieve this optimal bound of $q=Delta+1$. Previously, the best FPRAS requires $q>frac116Delta$ and the best deterministic FPTAS requires $q>2.581Delta+1$ for general graphs. In the case of $Delta=3$, the best previous result is an FPRAS for counting proper 5-colorings. We note that there is a barrier to go beyond $q=Delta+2$ for single-site Glauber dynamics based FPRAS and we overcome this by correlation decay approach. Moreover, we develop a number of new techniques for the correlation decay approach which can find applications in other approximate counting problems.

Full work available at URL: https://arxiv.org/abs/1611.04100

Recommendations

• Correlation decay and deterministic FPTAS for counting colorings of a graph
• On Approximately Counting Colorings of Small Degree Graphs
• Improved FPTAS for multi-spin systems
• Correlation decay and deterministic FPTAS for counting list-colorings of a graph
• Improved Exact Algorithms for Counting 3- and 4-Colorings

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Cited In (10)

• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
• Counting hypergraph colorings in the local lemma regime
• Uniqueness for the 3-state antiferromagnetic Potts model on the tree
• Improved FPTAS for multi-spin systems
• Frozen \((\Delta+1)\)-colourings of bounded degree graphs
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Correlation decay and deterministic FPTAS for counting list-colorings of a graph
• An FPTAS for the hardcore model on random regular bipartite graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Randomly coloring graphs of logarithmically bounded pathwidth

This page was built for publication: An FPTAS for counting proper four-colorings on cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575863)