THE CANONICAL TUTTE POLYNOMIAL FOR SIGNED GRAPHS.

We construct a new polynomial invariant for signed graphs, the trivari- ate Tutte polynomial, which contains among its evaluations the number of proper colorings and the number of nowhere-zero flows. In this, it parallels the Tutte poly- nomial of a graph, which contains the chromatic polynomial and flow polynomial as specializations. While the Tutte polynomial of a graph is equivalently defined as the dichromatic polynomial or Whitney rank polynomial, the dichromatic polynomial of a signed graph (defined more widely for biased graphs by Zaslavsky) does not, by contrast, give the number of nowhere-zero flows as an evaluation in general. The trivariate Tutte polynomial contains Zaslavsky's dichromatic polynomial as a spe- cialization. Furthermore, the trivariate Tutte polynomial gives as an evaluation the number of proper colorings of a signed graph under a more general sense of signed graph coloring in which colors are elements of an arbitrary finite set equipped with an involution. [ABSTRACT FROM AUTHOR]