What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am particularly interested in $k=2$. 


For planar balanced bipartite graphs (each color has to have same number of vertices assigned) the number of perfect matchings is $2^{O(n)}$ while for genus $\Omega(n^2)$ we can have $2^{\Omega(n\log n)}$. So is maximum number of perfect matchings $2^{O(n\log g)}$ for $k=2$?



Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph
Yes, but not for a great reason.


**Fact:** genus of a graph is bounded below by $|E|/6 - n/2+1$.


**Case 1:** suppose $|E| \leq 10 n$. Then the number of perfect matchings is at most ${ {|E|} \choose {n/2}} \leq 2^{|E|} \leq 2^{10n}.$


**Case 2:** suppose $|E| \geq 10n$ so that (by fact) the genus satisfies $g \geq n$. We know every graph has at most $2^{O(n \log(n))}$ perfect matchings, and we’re done since $g\geq n$.


