The rainbow matching conjecture (n,n)n1(n,n)\to n-1

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. Rainbow matching conjecture.

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

The conjecture is stated as a general-graph analogue of a bipartite conjecture, and the source notes that no counterexample is known in general graphs. If true, it would imply the Ryser–Brualdi–Stein conjecture on Latin transversals.

Sources & referencesView supporting material

Primary source

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

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.