On the algebraic complexity of some families of coloured Tutte polynomials

DOI10.1016/S0196-8858(03)00087-3zbMath1041.05042OpenAlexW2037760470MaRDI QIDQ1433009

Martin Lotz, Johann A. Makowsky

Publication date: 15 June 2004

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0196-8858(03)00087-3

zbMATH Keywords

partition functionIsing modelcoloured Tutte polynomial

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

A Dichotomy Theorem for Polynomial Evaluation, Algorithmic uses of the Feferman-Vaught theorem, Complexity of the Bollobás-Riordan Polynomial, Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, Complexity and approximability of the cover polynomial, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions, From a zoo to a zoology: Towards a general theory of graph polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Tutte polynomials computable in polynomial time
• A weighted graph polynomial from chromatic invariants of knots
• Gap-definable counting classes
• The complexities of the coefficients of the Tutte polynomial
• Completeness and reduction in algebraic complexity theory
• Counting problems over the reals
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• A symmetric function generalization of the chromatic polynomial of a graph
• Cook's versus Valiant's hypothesis
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• A Dichromatic Polynomial for Weighted Graphs and Link Polynomials
• A complexity theory based on Boolean algebra
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• A Tutte Polynomial for Coloured Graphs
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Randomised Approximation in the Tutte Plane
• On the computational complexity of the Jones and Tutte polynomials
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case