On Counting Generalized Colorings

The notion of graph polynomials definable in Monadic Second Order Logic, MSOL, was introduced by B. Courcelle, J.A. Makowsky and U. Rotics in 2001. It was shown later that the Tutte polynomial and generalizations of it, as well as the matching polynomial, the cover polynomial and the various interlace polynomials fall into this category. In this article we present a uniform model theoretic framework for studying graph polynomials. In particular we study an infinite class of graph polynomials based on counting functions of generalized colorings definable in full second order logic SOL.