%A Goodall, Andrew
%A Litjens, Bart
%A Regts, Guus
%A Vena, LluĂs
%D 2019
%T The canonical Tutte polynomial for signed graphs
%K
%X We construct a new polynomial invariant for signed graphs, the trivariate 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 polynomial 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 specialization. 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.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1233
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 749-754%V 88
%N 3
%@ 0862-9544
%8 2019-07-30