2017/03/07 by Johann A. Makowsky, Makowsky, J. A., Elena V. Ravve +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.1703.02297
openalex publication_date 2017/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.