Aharoni-Berger conjecture for graphs

Let M1,,MnM_1,\dots,M_n be matchings of size nn in a graph. A rainbow matching is a matching whose edges can be assigned distinct indices ii so that each edge belongs to MiM_i.

Aharoni-Berger conjecture. Every collection of nn matchings of size nn in a graph admits a rainbow matching of size n1n-1.

This drops the bipartiteness requirement from the preceding conjecture. The n1n-1 bound is best possible, as shown by the cycle construction described in the source, but the general assertion remains open in the supplied text.

Sources & referencesView supporting material

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).

Additional references

18 papers in this index state this conjecture (2012–2025). The statement above is taken from the most recent of them; the others are arXiv:2406.19873, arXiv:2204.08981, arXiv:2108.07734, arXiv:2012.14992, arXiv:2011.04650, arXiv:2003.08247, arXiv:2002.08974, arXiv:1710.04807, arXiv:1710.03041, arXiv:1709.02665, arXiv:1609.06346, arXiv:1601.00943, and 5 more.

Progress summary

Never refreshed

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.