Chip Removal for Computing the Number of Perfect Matchings

Аннотация

We consider a transformation of a graph G that replaces an induced subgraph H of arbitrary size by a small new subgraph h. We choose h in such a way that the equality M(G) = xM(G′) holds (where G′ is the new graph and the factor x depends on the numbers of matchings of H and its subgraphs). We describe how one can construct h when G is a plane graph and H is a bipartite graph (with some restriction on the coloring of the vertices connecting it with the other part of the graph G). For a plane bipartite graph H with a small number of such vertices, we prove that the equality holds for an arbitrary graph G.