The multicolored cycle matching conjecture
The multicolored cycle matching conjecture
Let be a cycle of length whose edges are colored with colors. Let and be the perfect matchings consisting of the even and odd edges, respectively, and let record the number of edges of each color in a matching . Let lie on the segment between and . The multicolored cycle matching conjecture. There is a matching of size at least such that
component-wise and
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 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.