It is well known that the number of proper k-colorings of a graph is a polynomial in k. We investigate in this talk under what conditions a numeric graph invariant which is parametrized with parameters K_1,..., k_m is a polynomial in these parameters. We give a sufficient conditions for this to happen which is general enough to encompass all the graph polynomials which are definable in Second Order Logic. This not only covers the various generalizations of the Tutte polynomials, Interlace polynomials, Matching polynomials, but allows us to identify new graph polynomials related to combinatorial problems discussed in the literature.
展开▼
