The canonical Tutte polynomial for signed graphs

Main Article Content

Andrew Goodall Bart Litjens Guus Regts Lluís Vena

Abstract

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.

Article Details

How to Cite
Goodall, A., Litjens, B., Regts, G., & Vena, L. (2019). The canonical Tutte polynomial for signed graphs. Acta Mathematica Universitatis Comenianae, 88(3), 749-754. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1233/722
Section
EUROCOMB 2019