The rainbow matching conjecture for general graphs

From papers

Let (m,n)k(m,n)\to k mean that every mm matchings of size nn in any graph have a rainbow matching of size kk. The notation (m,n)Bk(m,n)\to_{\mathcal{B}} k has the same meaning for bipartite graphs. Rainbow matching conjecture.

(2n,n)n.(2n,n)\to n.

If nn is odd, then

(2n1,n)n.(2n-1,n)\to n.

The bipartite analogue (2n1,n)Bn(2n-1,n)\to_{\mathcal{B}}n is known by Drisko's theorem. The conjecture asserts that passing from bipartite graphs to general graphs costs only one additional matching; it remains open in the supplied source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Ron Aharoni, Joseph Briggs, Jinha Kim and Minki Kim, “Badges and rainbow matchings”, arXiv:2004.07590 (2021).

Solutions 0

No solutions have been posted yet.