Aharoni-Berger strong conjecture for bipartite graphs
Let be matchings of size in a bipartite graph. A rainbow matching is a matching whose edges can be assigned distinct indices so that each edge belongs to .
Aharoni-Berger strong conjecture. Every collection of matchings of size in a bipartite graph admits a rainbow matching of size .
The extra edge in each matching permits a full rainbow matching and implies the preceding bipartite conjecture by adjoining a common dummy edge. The bound is best possible, while the conjecture remains open in the supplied text.
References
Primary source
Candida Bowtell, Andrea Freschi, Gal Kronenberg and Jun Yan, “A note on improved bounds for hypergraph rainbow matching problems”, arXiv:2501.03216 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.