Johann A. Makowsky (Technion Israel Institute of Technology)
Calvin Lab Room 116
Why Study Graph Polynomials? Algebraic vs. Graph Theoretic Properties of Graph Polynomials
We consider graph theoretic (semantic) and algebraic (syntactic) properties of graph polynomials. The chromatic polynomial also counts acyclic orderings is a typical graph theoretic property, whereas the recently proven unimodality of the absolute value of its coefficients is an algebraic property, and not graph theoretic. We examine many classical theorems from this point of view, which leads to interesting new questions and open problems.
Joint work with E.V. Ravve