Answers are grounded in this paper and cite their sources.
Finds conformal crosses in bipartite graphs with matching conditions, suggesting implications for 2-linkage problem algorithms.
A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B . A conformal cross over some cycle C is a pair of disjoint paths P₁ P 1 , P₂ P 2 which are internally disjoint from C , the endpoints of each path separate the endpoints of the other path on C , and both C∪ P₁∪ P₂ C ∪ P 1 ∪ P 2 and B-(V(C)∪ V(P₁)∪ V(P₂)) B - ( V ( C ) ∪ V ( P 1 ) ∪ V ( P 2 ) ) have a perfect matching. We show that if C is a 4-cycle in a brace B , then C has a a conformal cross if and only if B contains K3,3 K 3 , 3 as a matching minor. This result implies a polynomial time algorithm which solves the 2-linkage problem for alternating paths in bipartite graphs with perfect matchings.
No takes yet. Share an insight, caveat, or question.
Giannopoulou et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: