Approximating the chromatic polynomial is as hard as computing it exactly

DOI10.1007/s00037-023-00247-8arXiv2211.13790OpenAlexW4390986120MaRDI QIDQ6121107

Unnamed Author, Guus Regts, Ferenc Bencs

Publication date: 26 February 2024

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

planar graphschromatic polynomialTutte polynomialapproximate counting\#P-hardness

Mathematics Subject Classification ID

Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Holant problems for 3-regular graphs with complex edge functions
• Combinatorics and complexity of partition functions
• Inapproximability of the Tutte polynomial
• Factoring polynomials with rational coefficients
• The largest real zero of the chromatic polynomial
• Computing in the field of complex algebraic numbers
• The complexity of approximating complex-valued Ising and Tutte partition functions
• Inapproximability of the Tutte polynomial of a planar graph
• Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• The complexity of approximating the complex-valued Potts model
• Cayley trees do not determine the maximal zero-free locus of the independence polynomial
• On a conjecture of Sokal concerning roots of the independence polynomial
• Limiting measure of Lee-Yang zeros for the Cayley tree
• An inequality for the discriminant of a polynomial
• Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
• Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• An Inequality About Factors of Polynomials
• A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane
• The Zero-Free Intervals for Chromatic Polynomials of Graphs
• Density of Chromatic Roots in Minor-Closed Graph Families
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• On the computational complexity of the Jones and Tutte polynomials
• Chromatic Roots are Dense in the Whole Complex Plane
• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• The Complexity of Computing the Sign of the Tutte Polynomial
• Inapproximability of the Independent Set Polynomial in the Complex Plane
• The Computational Complexity of Tutte Invariants for Planar Graphs
• THE GOLDEN RATIO IN THE THEORY OF CHROMATIC POLYNOMIALS.
• Chromatic Polynomials
• The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
• On the location of chromatic zeros of series-parallel graphs