Farrell polynomials on graphs of bounded tree width

DOI10.1016/S0196-8858(02)00530-4zbMATH Open1023.68070MaRDI QIDQ1398293FDOQ1398293

Authors J. P. Mariño, Johann A. Makowsky 

Publication date 29 July 2003

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

zbMATH Keywords

computational complexitygenerating functionsmonadic second-order logicdefinabilitygraph polynomialscombinatorial enumerationFarrell polynomials

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Enumeration in graph theory (05C30)

Recommendations

• scientific article; zbMATH DE number 1504634
• scientific article; zbMATH DE number 1859215
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• Fubini numbers and polynomials of graphs
• Tree-Related Widths of Graphs and Hypergraphs
• Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Evaluating a weighted graph polynomial for graphs of bounded tree-width
• On the colored Tutte polynomial of a graph of bounded treewidth
• scientific article; zbMATH DE number 772777

Cites work

• scientific article; zbMATH DE number 3836093 (Why is no real title available?)
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 3127542 (Why is no real title available?)
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3783048 (Why is no real title available?)
• scientific article; zbMATH DE number 45266 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 733393 (Why is no real title available?)
• scientific article; zbMATH DE number 945671 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 1445310 (Why is no real title available?)
• scientific article; zbMATH DE number 3222645 (Why is no real title available?)
• A Tutte Polynomial for Coloured Graphs
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• An introduction to matching polynomials
• Clique polynomials and independent set polynomials of graphs
• Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Dependence polynomials
• Easy problems for tree-decomposable graphs
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• Graph characterising polynomials
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Le Polynôme De Martin D'un Graphe Eulerien
• Linear time solvable optimization problems on graphs of bounded clique-width
• Matching theory
• Mathematical foundations of computer science 1997. 22nd international symposium, MFCS '97, Bratislava, Slovakia, August 25--29, 1997. Proceedings
• New results for the Martin polynomial
• On a general class of graph polynomials
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• On the theory of the matching polynomial
• Problems in algebraic combinatorics
• The Complexity of Defining a Relation on a Finite Graph
• The complexity of computing the permanent
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• The parametrized complexity of knot polynomials

Cited in

(12)

• The parametrized complexity of knot polynomials
• Title not available (Why is no real title available?)
• Algorithmic uses of the Feferman-Vaught theorem
• Efficient computation of generalized Ising polynomials on graphs with fixed clique-width
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• An algorithm for calculating the independence and vertex-cover polynomials of a graph
• Linear Recurrence Relations for Graph Polynomials
• On the bivariate permanent polynomials of graphs
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width

This page was built for publication: Farrell polynomials on graphs of bounded tree width

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