The multicolored cycle matching conjecture
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.