The rainbow matching conjecture for general graphs
The rainbow matching conjecture for general graphs
Let mean that every matchings of size in any graph have a rainbow matching of size . The notation has the same meaning for bipartite graphs. Rainbow matching conjecture.
If is odd, then
The bipartite analogue 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
Sign in to submit a solution.
No solutions have been posted yet.