Tutte's dichromate for signed graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10421424" target="_blank" >RIV/00216208:11320/21:10421424 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=SjtMij5uZc" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=SjtMij5uZc</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2020.09.021" target="_blank" >10.1016/j.dam.2020.09.021</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Tutte's dichromate for signed graphs

Popis výsledku v původním jazyce

We introduce the trivariate Tutte polynomial of a signed graph as an invariant of signed graphs up to vertex switching that 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. The number of nowhere-zero tensions (for signed graphs they are not simply related to proper colorings as they are for graphs) is given in terms of evaluations of the trivariate Tutte polynomial at two distinct points. Interestingly, the bivariate dichromatic polynomial of a biased graph, shown by Zaslaysky to share many similar properties with the Tutte polynomial of a graph, does not in general yield the number of nowhere-zero flows of a signed graph. Therefore the &quot;dichromate&quot; for signed graphs (our trivariate Tutte polynomial) differs from the dichromatic polynomial (the rank-size generating function). The trivariate Tutte polynomial of a signed graph can be extended to an invariant of ordered pairs of matroids on a common ground set - for a signed graph, the cycle matroid of its underlying graph and its frame matroid form the relevant pair of matroids. This invariant is the canonically defined Tutte polynomial of matroid pairs on a common ground set in the sense of a recent paper of Krajewski, Moffatt and Tanasa, and was first studied by Welsh and Kayibi as a four-variable linking polynomial of a matroid pair on a common ground set. (C) 2020 Elsevier B.V. All rights reserved.

Název v anglickém jazyce

Tutte's dichromate for signed graphs

Popis výsledku anglicky

We introduce the trivariate Tutte polynomial of a signed graph as an invariant of signed graphs up to vertex switching that 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. The number of nowhere-zero tensions (for signed graphs they are not simply related to proper colorings as they are for graphs) is given in terms of evaluations of the trivariate Tutte polynomial at two distinct points. Interestingly, the bivariate dichromatic polynomial of a biased graph, shown by Zaslaysky to share many similar properties with the Tutte polynomial of a graph, does not in general yield the number of nowhere-zero flows of a signed graph. Therefore the &quot;dichromate&quot; for signed graphs (our trivariate Tutte polynomial) differs from the dichromatic polynomial (the rank-size generating function). The trivariate Tutte polynomial of a signed graph can be extended to an invariant of ordered pairs of matroids on a common ground set - for a signed graph, the cycle matroid of its underlying graph and its frame matroid form the relevant pair of matroids. This invariant is the canonically defined Tutte polynomial of matroid pairs on a common ground set in the sense of a recent paper of Krajewski, Moffatt and Tanasa, and was first studied by Welsh and Kayibi as a four-variable linking polynomial of a matroid pair on a common ground set. (C) 2020 Elsevier B.V. All rights reserved.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

289

Číslo periodika v rámci svazku

January

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

32

Strana od-do

153-184

Kód UT WoS článku

000596823800014

EID výsledku v databázi Scopus

2-s2.0-85092692997