On the algebraic complexity of some families of coloured Tutte polynomials
DOI10.1016/S0196-8858(03)00087-3zbMATH Open1041.05042OpenAlexW2037760470MaRDI QIDQ1433009FDOQ1433009
Authors: 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
Recommendations
- A Tutte Polynomial for Coloured Graphs
- The complexities of the coefficients of the Tutte polynomial
- Multivariable, parameterized, and colored extensions of the Tutte polynomial
- On the computational complexity of the Jones and Tutte polynomials
- On the complexity of generalized chromatic polynomials
- The exact complexity of the Tutte polynomial
- Some algebraic structures related to the Tutte polynomial
- On the Tutte polynomial
- On the colored Tutte polynomial of a graph of bounded treewidth
- \(T\)-chromatic polynomials
Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- A weighted graph polynomial from chromatic invariants of knots
- A symmetric function generalization of the chromatic polynomial of a graph
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Title not available (Why is that?)
- Approximation algorithms for NP-hard problems.
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of computing the permanent
- Title not available (Why is that?)
- On the computational complexity of the Jones and Tutte polynomials
- Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
- Title not available (Why is that?)
- Completeness and reduction in algebraic complexity theory
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Tutte Polynomial for Coloured Graphs
- Title not available (Why is that?)
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- Title not available (Why is that?)
- Counting problems over the reals
- Gap-definable counting classes
- A Dichromatic Polynomial for Weighted Graphs and Link Polynomials
- Title not available (Why is that?)
- Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- Tutte polynomials computable in polynomial time
- Cook's versus Valiant's hypothesis
- A complexity theory based on Boolean algebra
- Randomised Approximation in the Tutte Plane
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexities of the coefficients of the Tutte polynomial
- Title not available (Why is that?)
Cited In (10)
- Complexity of the Bollobás-Riordan Polynomial
- A Dichotomy Theorem for Polynomial Evaluation
- Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
- Algorithmic uses of the Feferman-Vaught theorem
- How I got to like graph polynomials
- Complexity and approximability of the cover polynomial
- Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
- A Subset Expansion of the Coloured Tutte Polynomial
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
This page was built for publication: On the algebraic complexity of some families of coloured Tutte polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1433009)
