تقرير
A Hall-type condition for path covers in bipartite graphs
العنوان: | A Hall-type condition for path covers in bipartite graphs |
---|---|
المؤلفون: | Lavrov, Mikhail, Vandenbussche, Jennifer |
سنة النشر: | 2023 |
المجموعة: | Mathematics |
مصطلحات موضوعية: | Mathematics - Combinatorics, 05C38 |
الوصف: | 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\Lambda(S)|$, where $S\subseteq X$ and $\mathsf\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. |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2310.05248 |
رقم الأكسشن: | edsarx.2310.05248 |
قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!