25 December 2008
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
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. © 2008 Springer-Verlag Berlin Heidelberg.
Submitted to ORA: