Skip to main content
1 of 2

I think that the Tutte polynomial, as suggested by Fedor Petrov in the comments, is likely what you are looking for. For a graph $G$, this is the polynomial $$ T(x, y) = \sum_{A \subseteq E(G)} (x-1)^{k(A) - k(E)} (y-1)^{k(A) + |A| - |V(G)|}$$ where $k(A)$ is the number of connected components of $(V(G), A)$. Indeed, the Tutte polynomial is well defined for any [matroid][1], including the [graphic matroid][2] $M(G)$ induced by any graph $G$, and in this case equals the above polynomial. There is no restriction on $G$ not being a multigraph in either of these two definitions.

The primary reason why it generalizes the chromatic polynomial for a graph is due to the fact that evaluation at $y=0$ of the Tutte polynomial is closely related to the chromatic polynomial. More specifically, $$ \chi_G(\lambda) = (-1)^{|V(G)| - k(G)} \lambda^{k(G)} T_G(1 - \lambda, 0)$$ In fact, just as deletion-contraction holds for the chromatic polynomial, it too does for the Tutte polynomial. The above specialization to the chromatic polynomial is only one of many of the Tutte polynomial, and there is a great deal of interesting material to be found online regarding it. [1]: https://en.wikipedia.org/wiki/Matroid [2]: https://en.wikipedia.org/wiki/Graphic_matroid