Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950668 | Information and Computation | 2017 | 12 Pages |
Abstract
The main technical innovation is a variant of Hall's Lemma. We show that in bipartite graphs with bipartition (L,R) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW-matchings, provided that L expands in R by a factor of (2âϵ), for ϵ<15.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, Paul Wollan,