Barát–Gyárfás–Sárközy conjecture for rainbow matchings in multigraphs

Let GG be a properly edge-colored multigraph with 2ntn2n-t_n colors and exactly nn edges of each color, where

tn={0if n is even,1if n is odd.t_n=\begin{cases}0&\text{if }n\text{ is even},\\1&\text{if }n\text{ is odd}. \end{cases}

Barát–Gyárfás–Sárközy conjecture. Then GG has a rainbow matching using nn colors.

The conjecture concerns the number of colors needed when every color class has exactly nn edges. The source cites best-known partial results, but does not state a resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Debsoumya Chakraborti and Po-Shen Loh, “Large rainbow matchings in edge-colored graphs”, arXiv:2011.04650 (2026).

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.