Combinatorica Вычислительная математика
Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses
Аннотация
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.