The multicolored cycle matching conjecture

Let GG be a cycle of length 22\ell whose edges are colored with hh colors. Let M0M_0 and M1M_1 be the perfect matchings consisting of the even and odd edges, respectively, and let pMZ+hp_M\in\mathbb Z_+^h record the number of edges of each color in a matching MM. Let kZhk\in\mathbb Z^h lie on the segment between pM0p_{M_0} and pM1p_{M_1}. The multicolored cycle matching conjecture. There is a matching MM of size at least h+2\ell-h+2 such that

pMkp_M\leq k

component-wise and

pMk1h2.\lVert p_M-k\rVert_1\leq h-2.

The paper presents this as a generalization of the corresponding three-color result and as a possible ingredient for extending the approximation guarantee to graphs with a constant number h4h\geq4 of colors. Its resolution is not given in the supplied text.

Sources & referencesView supporting material

Primary source

Manuel Aprile and Marco Di Summa, “The red-blue-yellow matching problem”, arXiv:2603.18754 (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.