Abstract
A k-valuation is a special type of edge k-colouring of a medial graph. Various graph polynomials, such as the Tutte, Penrose, Bollob\'as-Riordan, and transition polynomials, admit combinatorial interpretations and evaluations as weighted counts of k-valuations. In this paper, we consider a multivariate generating function of k-valuations. We show that this is a polynomial in k and hence defines a graph polynomial. We then show that the resulting polynomial has several desirable properties, including a recursive deletion-contraction-type definition, and specialises to the graph polynomials mentioned above. It also offers an alternative extension of the Penrose polynomial from plane graphs to graphs in other surfaces.
Original language | English |
---|---|
Pages (from-to) | 290-305 |
Number of pages | 16 |
Journal | Australasian Journal of Combinatorics |
Volume | 72 |
Issue number | 2 |
Publication status | Published - Oct 2018 |
Keywords
- math.CO
- 05C31