2015/08/04 by Thomas Krajewski, Iain Moffatt, Adrian Tanasă +1
Mathematics · #Advanced Combinatorial Mathematics #Algebraic structures and combinatorial models #Alternating polynomial #Chromatic polynomial #Combinatorics #Discrete mathematics #Geometric and Algebraic Topology #Graph #Line graph #Mathematics #Matrix polynomial #Polynomial #Reciprocal polynomial #Tutte polynomial #Voltage graph #math.CO
paper · pdf · doi:10.1016/j.aam.2017.12.00
published as Advances in Applied Mathematics, 95 (2018) 271--330 · v2: change of title and some reordering
openalex publication_date 2015/08/04 · arxiv created 2017/12/18 · arxiv updated 2018/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
By considering Tutte polynomials of Hopf algebras, we show how a Tutte polynomial can be canonically associated with combinatorial objects that have some notions of deletion and contraction. We show that several graph polynomials from the literature arise from this framework. These polynomials include the classical Tutte polynomial of graphs and matroids, Las Vergnas' Tutte polynomial of the morphism of matroids and his Tutte polynomial for embedded graphs, Bollobas and Riordan's ribbon graph polynomial, the Krushkal polynomial, and the Penrose polynomial. We show that our Tutte polynomials of Hopf algebras share common properties with the classical Tutte polynomial, including deletion-contraction definitions, universality properties, convolution formulas, and duality relations. New results for graph polynomials from the literature are then obtained as examples of the general results. Our results offer a framework for the study of the Tutte polynomial and its analogues in other settings, offering the means to determine the properties and connections between a wide class of polynomial invariants.