In the mathematical fields of graph theory and combinatorics, a matching polynomial (sometimes called an acyclic polynomial) is a generating function of the numbers of matchings of various sizes in a graph.
Let G be a graph with n vertices and let mk be the number of k-edge matchings.
The matching polynomial of a graph G with n vertices is related to that of its complement by a pair of (equivalent) formulas.
In particular, computing the matching polynomial on n-vertex graphs of treewidth k is fixed-parameter tractable: there exists an algorithm whose running time, for any fixed constant k, is a polynomial in n with an exponent that does not depend on k (Courcelle, Makowsky & Rotics 2001).
The matching polynomial of a graph with n vertices and clique-width k may be computed in time nO(k) (Makowsky et al. 2006).