From a zoo to a zoology: Towards a general theory of graph polynomials

DOI10.1007/s00224-007-9022-9zbMath1162.68502OpenAlexW1983907004MaRDI QIDQ1015377

Johann A. Makowsky

Publication date: 8 May 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9022-9

zbMATH Keywords

descriptive complexitygraph polynomialscombinatorial counting functions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

In praise of homomorphisms, A Graph Polynomial for Independent Sets of Bipartite Graphs, Strongly polynomial sequences as interpretations, A survey on recurrence relations for the independence polynomial of hypergraphs, Border correlations, lattices, and the subgraph component polynomial, Border Correlations, Lattices, and the Subgraph Component Polynomial, Complexity of the Bollobás-Riordan Polynomial, Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, Polynomial graph invariants from homomorphism numbers, Complexity and approximability of the cover polynomial, The enumeration of vertex induced subgraphs with respect to the number of components, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, The Equivalence of Two Graph Polynomials and a Symmetric Function, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, On the complexity of generalized chromatic polynomials, Efficient computation of the characteristic polynomial of a tree and related tasks, A logician's view of graph polynomials, Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions, Semantic Equivalence of Graph Polynomials Definable in Second Order Logic, An extension of the bivariate chromatic polynomial, Squares and primitivity in partial words, Almost unimodal and real-rooted 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A two-variable interlace polynomial
• Algorithmic uses of the Feferman-Vaught theorem
• Tutte polynomials computable in polynomial time
• Elements of finite model theory.
• The interlace polynomial of a graph
• A Tutte polynomial for signed graphs
• The matching polynomial of a polygraph
• Reducibility by algebraic projections
• Colorings and orientations of graphs
• Clique polynomials and independent set polynomials of graphs
• Metafinite model theory
• Farrell polynomials on graphs of bounded tree width
• Interlace polynomials
• The Go polynomials of a graph.
• Graph-polynomials
• On the algebraic complexity of some families of coloured Tutte polynomials
• Completeness and reduction in algebraic complexity theory
• New results for the Martin polynomial
• Counting problems over the reals
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Coloring mixed hypergraphs: theory, algorithms and applications
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• A symmetric function generalization of the chromatic polynomial of a graph
• The parametrized complexity of knot polynomials
• Chromatic polynomials and the symmetric group
• On the cover polynomial of a digraph
• The path-cycle symmetric function of a digraph
• Acyclic orientations of graphs
• Dependence polynomials
• PP is as Hard as the Polynomial-Time Hierarchy
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• Hard Enumeration Problems in Geometry and Combinatorics
• Tutte Polynomials and Link Polynomials
• The Complexity of Enumeration and Reliability Problems
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Graph colorings with local constraints -- a survey
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• A Tutte Polynomial for Coloured Graphs
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On the computational complexity of the Jones and Tutte polynomials
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Complexity of the Cover Polynomial
• Graph-Theoretic Concepts in Computer Science
• Logical Approaches to Computational Barriers
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic