Graph polynomials derived from Tutte–Martin polynomials Original Research Article

A graph polynomial image has recently been studied by Arratia et al. [The interlace polynomial: a new graph polynomial, in: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Mathematics, San Francisco, CA, 2000, North-Holland, Amsterdam, pp. 237–245]. That polynomial can be derived from the restricted Tutte–Martin polynomial of an isotropic system, which we introduced [A. Bouchet, Tutte–Martin polynomials and orienting vectors of isotropic systems, Graphs Combin. 7 (1991) 235–252] in order to prove a conjecture of Las Vergnas on the Tutte polynomial of a binary matroid. It follows that (i) image is equal to a power of 2 and (ii) image is the same power of 2 times an odd integer. Neither (i) or (ii) appears in [R. Arratia et al., The interlace polynomial: a new graph polynomial, in: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Mathematics, San Francisco, CA, 2000, North-Holland, Amsterdam, pp. 237–245].