Semantic equivalence of graph polynomials definable in second order logic

DOI10.1007/978-3-662-52921-8_18MaRDI QIDQ2820700zbMATH OpenOpenAlexFDO

Authors Johann A. Makowsky, E. Ravve

Publication date 9 September 2016

Published in Logic, Language, Information, and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-52921-8_18

Mathematics Subject Classification ID

Higher-order logic (03B16) Graph polynomials (05C31)

Recommendations

• A logician's view of graph polynomials
• Logical Approaches to Computational Barriers
• From a zoo to a zoology: Towards a general theory of graph polynomials
• The graph polynomials and their equivalence
• On counting generalized colorings

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A computational framework for the study of partition functions and graph polynomials
• A Contribution to the Theory of Chromatic Polynomials
• A criterion for the half-plane property
• A weighted graph polynomial from chromatic invariants of knots
• Algorithmic uses of the Feferman-Vaught theorem
• An extension of the bivariate chromatic polynomial
• Application of logic to combinatorial sequences and their recurrence relations
• Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• Chromatic Roots are Dense in the Whole Complex Plane
• Clique polynomials and independent set polynomials of graphs
• Clique polynomials have a unique root of smallest modulus
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Graph polynomials and their applications. I: The Tutte polynomial
• Graph polynomials: from recursive definitions to subset expansion formulas
• Homogeneous multivariate polynomials with the half-plane property
• scientific article; zbMATH DE number 434899 (Why is no real title available?)
• scientific article; zbMATH DE number 3547324 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
• Lee-Yang theorems and the complexity of computing averages
• Linear matrix inequality representation of sets
• Matching theory
• Multivariate stable polynomials: theory and applications
• Necessary and sufficient conditions for the Hurwitz and Schur stability of interval matrices
• Negative dependence and the geometry of polynomials
• On counting generalized colorings
• On sequences of polynomials arising from graph invariants
• On stability of Alexander polynomials of knots and links (survey)
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• On the location of roots of graph polynomials
• On the location of roots of independence polynomials
• On the roots of edge cover polynomials of graphs
• On the theory of the matching polynomial
• Polynomials with the half-plane property and matroid theory
• Spectra of graphs
• The equivalence of two graph polynomials and a symmetric function
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The roots of the independence polynomial of a clawfree graph
• Tutte Polynomials and Link Polynomials

Cited in

(5)

• A logician's view of graph polynomials
• scientific article; zbMATH DE number 4124985 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• My writing
• Graph polynomials: some questions on the edge

This page was built for publication: Semantic equivalence of graph polynomials definable in second order logic

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