Two Disjoint Alternating Paths in Bipartite Graphs

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 and a cycle C in B is called conformal if B-V(C) has a perfect matching. We show that there do not exist two disjoint alternating paths that form a cross ov...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-10
Main Authors: Giannopoulou, Archontia C, Wiederrecht, Sebastian
Format: Article
Language:English
Subjects:
Algorithms
Graph theory
Graphs
Matching
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 and a cycle C in B is called conformal if B-V(C) has a perfect matching. We show that there do not exist two disjoint alternating paths that form a cross over a conformal cycle C in a brace B if and only if one can reduce B, by an application of a matching theoretic analogue of small clique sums, to a planar brace H in which C bounds a face. We then utilise this result and provide a polynomial time algorithm which solves the 2-linkage problem for alternating paths in bipartite graphs with perfect matchings.
ISSN:2331-8422