Tutte polynomials of vertex-weighted graphs and group cohomology
The classical Tutte polynomial \(T_{G}(x,y)\) of a graph \(G\) initially appeared in the combinatorial theory of graphs as a generalization of a recurrence relation discovered by Whitney and Birkhoff for the number of proper colorings of a graph in \(n\) colors. The polynomial thus defined turns out to be related to many important graph invariants: the number of proper colorings in \(n\) colors, the number of \(n\)-flows, the number of spanning trees, the number of dimers (one-factors), etc.. Therefore, the theory of the Tutte polynomial was highly developed and generalized in many ways. The classical Tutte polynomial is discussed and defined recursively via deletion-contraction relations. The authors generalized the classical relation. Here, the authors constructed a generalization of the Tutte polynomial for vertex-weighted graphs for which the coefficients of the deletion-contraction relation depend nontrivially on the vertex weights. They showed that the corresponding relation on the coefficients coincides with the two-cocycle relation in the group cohomology. Also, they obtained a representation of a new invariant by summing over subgraphs and established its connection with four-invariants of graphs.
scientific article; zbMATH DE number 7364290
scientific article