Combinatorica Вычислительная математика

Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses

Archontia C. Giannopoulou, Sebastian Wiederrecht
Springer Nature · 2026-05-04 · DOI 10.1007/s00493-026-00211-4

Аннотация

Abstract 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_1$$ P 1 , $$P_2$$ 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\cup P_1\cup P_2$$ C ∪ P 1 ∪ P 2 and $$B-(V(C)\cup V(P_1)\cup V(P_2))$$ 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 $$K_{3,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.

Читать у издателя →