An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
From MaRDI portal
Publication:4575863
DOI10.1137/1.9781611974782.117zbMath1410.05207arXiv1611.04100OpenAlexW2950027515MaRDI QIDQ4575863
Minshen Zhu, Pinyan Lu, Kuan Yang, Chihao Zhang
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.04100
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (8)
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs ⋮ An FPTAS for the hardcore model on random regular bipartite graphs ⋮ Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials ⋮ Unnamed Item ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Uniqueness for the 3-state antiferromagnetic Potts model on the tree ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Frozen (Δ + 1)-colourings of bounded degree graphs
This page was built for publication: An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
