A Hall-Type Condition for Path Covers in Bipartite Graphs

Let G be a bipartite graph with bipartition ( X, Y ). Inspired by a hypergraph problem posed by Kostochka et al. (2021), we seek an upper bound on the number of disjoint paths needed to cover all the vertices of X . We conjecture that a Hall- type sufficient condition holds based on the maximum value of S- Lambda ( S ) , where S C X and Lambda ( S ) is the set of all vertices in Y with at least two neighbors in S . This condition is also a necessary one for a hereditary version of the problem, where we delete vertices from X and try to cover the remaining vertices by disjoint paths. The conjecture holds when G is a forest, has maximum degree 3, or is regular with high girth, and we prove those results in this paper.