A Vertex-Weighted Tutte Symmetric Function, and Constructing Graphs with Equal Chromatic Symmetric Function Article Swipe

View

Related Concepts

Chromatic polynomial Combinatorics Tutte polynomial Mathematics Chromatic scale Symmetric function Vertex (graph theory) Spanning tree Discrete mathematics Graph Line graph Voltage graph

Logan Crew , Sophie Spirkl ·

YOU? · · 2020 · Open Access · · OA: W3045345952

This paper has two main parts. First, we consider the Tutte symmetric function $XB$, a generalization of the chromatic symmetric function. We introduce a vertex-weighted version of $XB$ and show that this function admits a deletion-contraction relation. We also demonstrate that the vertex-weighted $XB$ admits spanning-tree and spanning-forest expansions generalizing those of the Tutte polynomial by connecting $XB$ to other graph functions. Second, we give several new methods for constructing nonisomorphic graphs with equal chromatic symmetric function, and provide the first examples of nonisomorphic graphs that are not distinguished by the Tutte symmetric function.