Skip to main content
removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Upper bound on the number of Perfect Matchingsperfect matchings in $K_{3,3}$-free graphs

Source Link

Upper bound on the number of Perfect Matchings in $K_{3,3}$-free graphs

Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a partition of the set of vertices $V$ onto disjoint two-element subsets according to edges $E$.

Question: Are there any known upper bounds for the number of perfect matchings of such graphs?

I am not a specialist in graph theory and after an extensive internet search, I was only able to find that the complexity of computing perfect matchings for such $K_{3,3}$-free graphs is lower than the one in the general case (it reduces to NC from beeing #P hard).

Motivation: I stumbled on this problem while studying an unrelated physics problem that concerns contextuality in a restricted model of quantum computing based on Majorana fermions (see for example this work by Bravyi).