A finite simple connected graph $\Gamma$ with vertices $V(\Gamma)$ has a partition of its vertices into (at most) two subsets defined as follows: Given a spanning tree $T\subset \Gamma$, chose a function $\varphi_T:V(\Gamma)\longrightarrow \lbrace \pm 1\rbrace$ such that $\varphi(s)\varphi(t)=-1$ if $s,t\in V(\Gamma)$ are adjacent vertices of $T$. The product $\psi=\prod_T\varphi_T$ over all spanning trees of $\Gamma$ is well defined up to a global sign and induces a partition $\psi^{-1}(1)\cup\psi^{-1}(-1)$ of $V(\Gamma)$.

Is there an efficient way for computing this partition for an arbitrary graph?

Remark: The best way I can think of for a general graph is to consider all partitions $A\cup B$ of $V(\Gamma)$ which induce a connected bipartite subgraph (obtained by removing all edges having either both endpoints in $A$ or in $B$) of odd complexity.

4more comments