On six expressions of the Tutte polynomial of a graph (on a linearly ordered set of edges)

Emeric Gioan 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : I will present six interrelated general expressions of the Tutte polynomial of a graph, that are available as soon as the set of edges is linearly ordered, and that witness combinatorial properties of such a graph: - the classical enumeration of spanning tree activities; - its refinement into a four variable expression in terms of subset activities (that corresponds to the classical partition of the set of edge subsets into boolean intervals); - the enumeration of orientation-activities for directed graphs; - its refinement into a four variable expression in terms of subset orientation-activities (that corresponds to the partition of the set of orientations into active partition reversal classes); - the convolution formula for the Tutte polynomial (that does not need the graph to be ordered); - and an expression of the Tutte polynomial using only beta invariants of minors (that refines the above expressions). I will mention that these expressions are all interrelated by the canonical active bijection between spanning trees and orientations, subject of a long-term joint work with Michel Las Vergnas.
Type de document :
Communication dans un congrès
Graph Polynomials: Towards a Comparative Theory, Jun 2016, Dagstuhl seminar, Germany. 2016
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370263
Contributeur : Emeric Gioan <>
Soumis le : jeudi 22 septembre 2016 - 11:56:56
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-01370263, version 1

Collections

Citation

Emeric Gioan. On six expressions of the Tutte polynomial of a graph (on a linearly ordered set of edges). Graph Polynomials: Towards a Comparative Theory, Jun 2016, Dagstuhl seminar, Germany. 2016. 〈lirmm-01370263〉

Partager

Métriques

Consultations de la notice

50