Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width

DOI10.1016/J.DAM.2004.01.016MaRDI QIDQ1764811zbMATH OpenOpenAlexFDO

Authors Johann A. Makowsky

Publication date 22 February 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2004.01.016

zbMATH Keywords

Tutte polynomialCombinatorial enumerationFixed parameter complexityKnot polynomials

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15)

Cites work

• scientific article; zbMATH DE number 1670492 (Why is no real title available?)
• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 3941493 (Why is no real title available?)
• scientific article; zbMATH DE number 34890 (Why is no real title available?)
• scientific article; zbMATH DE number 53949 (Why is no real title available?)
• scientific article; zbMATH DE number 67324 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1323192 (Why is no real title available?)
• scientific article; zbMATH DE number 1057883 (Why is no real title available?)
• scientific article; zbMATH DE number 1088200 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 795115 (Why is no real title available?)
• scientific article; zbMATH DE number 795683 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 820875 (Why is no real title available?)
• scientific article; zbMATH DE number 1437928 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A Tutte Polynomial for Coloured Graphs
• A Tutte polynomial for signed graphs
• A spanning tree expansion of the Jones polynomial
• Algorithmic uses of the Feferman-Vaught theorem
• Algorithmic versus axiomatic definitions of matroids
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Application of model theoretic games to discrete linear orders and finite automata
• COMPUTING THE JONES POLYNOMIAL ON BIPARTITE GRAPHS
• Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Completeness and reduction in algebraic complexity theory
• Decomposition of regular matroids
• Directed tree-width
• Easy problems for tree-decomposable graphs
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• Farrell polynomials on graphs of bounded tree width
• Fusion in relational structures and the verification of monadic second-order properties
• Kauffman's polynomial and alternating links
• Modal languages and bounded fragments of predicate logic
• Monotone monadic SNP and constraint satisfaction
• On the algebraic complexity of some families of coloured Tutte polynomials
• On the computational complexity of the Jones and Tutte polynomials
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Polynomial Invariants of Graphs
• Polynomials for Links
• Reduction algorithms for graphs of small treewidth
• Splitting formulas for Tutte polynomials
• The first order properties of products of algebraic systems
• The fourth Skein Module and the Montesinos-Nakanishi Conjecture for 3-algebraic links
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• The parametrized complexity of knot polynomials
• Tutte Polynomials and Link Polynomials
• Tutte polynomials computable in polynomial time
• Upper bounds to the clique width of graphs

Cited in

(20)

• The enumeration of vertex induced subgraphs with respect to the number of components
• Harary polynomials
• Computing HOMFLY polynomials of 2-bridge links from 4-plat representation
• An extension of the bivariate chromatic polynomial
• Jones polynomial of knots formed by repeated tangle replacement operations
• A little statistical mechanics for the graph theorist
• Recurrence relations for graph polynomials on bi-iterative families of graphs
• On the colored Tutte polynomial of a graph of bounded treewidth
• The Treewidth and Pathwidth of Graph Unions
• Computing a link diagram from its exterior
• Connection Matrices for MSOL-Definable Structural Invariants
• Courcelle's theorem for triangulations
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Counting truth assignments of formulas of bounded tree-width or clique-width
• A logician's view of graph polynomials
• A Most General Edge Elimination Polynomial
• Fixed-parameter tractability of treewidth and pathwidth
• The HOMFLY-PT polynomial is fixed-parameter tractable
• How I got to like graph polynomials
• Evaluations of Graph Polynomials

This page was built for publication: Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width

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