A logician's view of graph polynomials
From MaRDI portal
Publication:2273013
Abstract: Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. We discuss how to represent and compare graph polynomials by their distinctive power. We introduce the class of graph polynomials definable using Second Order Logic which comprises virtually all examples of graph polynomials with a fixed finite set of indeterminates. Finally we show that the location of zeros and stability of graph polynomials is not a semantic property. The paper emphasizes a model theoretic view and gives a unified exposition of classical results in algebraic combinatorics together with new and some of our previously obtained results scattered in the graph theoretic literature.
Recommendations
Cites work
- scientific article; zbMATH DE number 3836093 (Why is no real title available?)
- scientific article; zbMATH DE number 434899 (Why is no real title available?)
- scientific article; zbMATH DE number 3885934 (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?)
- scientific article; zbMATH DE number 1912564 (Why is no real title available?)
- scientific article; zbMATH DE number 2121498 (Why is no real title available?)
- scientific article; zbMATH DE number 803291 (Why is no real title available?)
- scientific article; zbMATH DE number 272725 (Why is no real title available?)
- scientific article; zbMATH DE number 2199828 (Why is no real title available?)
- A Contribution to the Theory of Chromatic Polynomials
- A computational framework for the study of partition functions and graph 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
- Chromatic invariants for finite graphs: Theme and polynomial variations
- Clique polynomials and independent set polynomials of graphs
- Clique polynomials have a unique root of smallest modulus
- Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- Connection matrices and the definability of graph parameters
- Connections between the matching and chromatic polynomials
- Elements of finite model theory.
- Evaluations of Graph Polynomials
- 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
- Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
- Hyperbolicity and stable polynomials in combinatorics and probability
- 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 counting generalized colorings
- On sequences of polynomials arising from graph invariants
- On the complexity of generalized chromatic polynomials
- 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
- Polynomial graph invariants from homomorphism numbers
- Polynomials with the half-plane property and matroid theory
- Semantic equivalence of graph polynomials definable in second order logic
- Spectra of graphs
- Strongly polynomial sequences as interpretations
- 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
- The universal edge elimination polynomial and the dichromatic polynomial
- Theory of monomer-dimer systems
- Tutte Polynomials and Link Polynomials
- Tutte-Whitney polynomials: some history and generalizations
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
Cited in
(9)- Weakly distinguishing graph polynomials on addable properties
- Semantic equivalence of graph polynomials definable in second order logic
- Harary polynomials
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Almost unimodal and real-rooted graph polynomials
- Planar polynomial of the graphs
- Graph polynomials: from recursive definitions to subset expansion formulas
- Logical Approaches to Computational Barriers
- Evaluations of Graph Polynomials
This page was built for publication: A logician's view of graph polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2273013)
