E. Yu. Lerner
Published 2024-04-14Version 1
In 1977, Yu.V. Matiyasevich proposed a formula expressing the chromatic polynomial of an arbitrary graph as a linear combination of flow polynomials of subgraphs of the original graph. In this paper, we prove that this representation is a particular case of one (easily verifiable) formula, namely, the representation of the characteristic polynomial of an arbitrary matroid as a linear combination of characteristic polynomials of dual matroids. As applications, we consider an explicit expression for the flow polynomial of a complete graph and a formula for the characteristic polynomial of the matroid dual to the matroid of the projective geometry over a finite field. We prove, in particular, that their major coefficients are defined by the beginning of a certain row in the Pascal triangle. We study in detail the connection with convolution formulas and other results for Tutte polynomials.
A new application of the $\otimes_h$-product to $α$-labelings
An application of a bijection of Mansour, Deng, and Du
An application of the Local C(G,T) Theorem to a conjecture of Weiss
![QR code for arXiv:2404.09347 [math.CO]](http://oss.arxitics.com/images/favicon.svg)