2023/10/08 by M. I. Lavrov, Lavrov, Mikhail, Jennifer Vandenbussche +1
Computer Science · Mathematics · Engineering · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2310.05248
Let G be a bipartite graph with bipartition (X,Y). Inspired by a hypergraph problem, 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|-|\mathsfΛ(S)|, where S⊆ X and \mathsfΛ(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.