A logician's view of graph polynomials

DOI10.1016/J.APAL.2019.04.007zbMATH Open1477.03122arXiv1703.02297OpenAlexW2963691321WikidataQ128116912 ScholiaQ128116912MaRDI QIDQ2273013FDOQ2273013

Johann A. Makowsky, Tomer Kotek, E. Ravve

Publication date: 18 September 2019

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1703.02297

zbMATH Keywords

generating functionsgraph polynomialsgraph invariantschromatic polynomialsdistinguishing powerzeros of graph polynomials

Mathematics Subject Classification ID

Graph polynomials (05C31) Model theory of finite structures (03C13)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A weighted graph polynomial from chromatic invariants of knots
• The Equivalence of Two Graph Polynomials and a Symmetric Function
• A Contribution to the Theory of Chromatic Polynomials
• Matching theory
• Spectra of graphs
• Chromatic invariants for finite graphs: Theme and polynomial variations
• Theory of monomer-dimer systems
• An extension of the bivariate chromatic polynomial
• Homogeneous multivariate polynomials with the half-plane property
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• Graph Polynomials and Their Applications I: The Tutte Polynomial
• On the theory of the matching polynomial
• On the location of roots of independence polynomials
• On the roots of edge cover polynomials of graphs
• Elements of finite model theory.
• Clique polynomials and independent set polynomials of graphs
• Multivariate stable polynomials: theory and applications
• Negative dependence and the geometry of polynomials
• The roots of the independence polynomial of a clawfree graph
• Clique polynomials have a unique root of smallest modulus
• Linear matrix inequality representation of sets
• Chromatic Roots are Dense in the Whole Complex Plane
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A criterion for the half-plane property
• Evaluations of Graph Polynomials
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Strongly polynomial sequences as interpretations
• Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products
• On the location of roots of graph polynomials
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Lee-Yang theorems and the complexity of computing averages
• Algorithmic uses of the Feferman-Vaught theorem
• Tutte Polynomials and Link Polynomials
• Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures
• Polynomials with the half-plane property and matroid theory
• On Counting Generalized Colorings
• Graph polynomials: from recursive definitions to subset expansion formulas
• On sequences of polynomials arising from graph invariants
• Connection matrices and the definability of graph parameters
• A Computational Framework for the Study of Partition Functions and Graph Polynomials
• On the complexity of generalized chromatic polynomials
• Hyperbolicity and stable polynomials in combinatorics and probability
• Connections between the matching and chromatic polynomials
• Necessary and sufficient conditions for the Hurwitz and Schur stability of interval matrices
• Semantic Equivalence of Graph Polynomials Definable in Second Order Logic
• The universal edge elimination polynomial and the dichromatic polynomial

Cited In (5)

• Weakly distinguishing graph polynomials on addable properties
• Almost unimodal and real-rooted graph polynomials
• Planar polynomial of the graphs
• Harary polynomials
• From a zoo to a zoology: Towards a general theory 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)