Identities for circuit partition polynomials, with applications to the Tutte polynomial

AbstractThe Martin polynomials, introduced by Martin in his 1977 thesis, encode information about the families of circuits in Eulerian graphs and digraphs. The circuit partition polynomials, J(G;x) and j(G→;x), are simple transformations of the Martin polynomials. We give new identities for these polynomials, analogous to Tutte's identity for the chromatic polynomial. Following a useful expansion of Bollobás [J. Combin. Theory Ser. B 85 (2002) 261–268], these formulas give combinatorial interpretations for all integer evaluations of the circuit partition and Martin polynomials. Selected evaluations of the formulas give combinatorial identities that expose the structure and relations of Eulerian graphs and digraphs. New identities and combinatorial interpretations for all integer values of the Tutte polynomial of a planar graph along the line y=x also follow from these results