  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.
