Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8904737 | Advances in Mathematics | 2018 | 45 Pages |
Abstract
Aharoni and Berger conjectured that in every proper edge-colouring of a bipartite multigraph by n colours with at least n+1 edges of each colour there is a rainbow matching using every colour. This conjecture generalizes a longstanding problem of Brualdi and Stein about transversals in Latin squares. Here an approximate version of the Aharoni-Berger Conjecture is proved-it is shown that if there are at least n+o(n) edges of each colour in a proper n-edge-colouring of a bipartite multigraph then there is a rainbow matching using every colour.
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematics (General)
Authors
Alexey Pokrovskiy,