Pardey and Rautenbach's bounded-deviation conjecture for colour-balanced matchings
Pardey and Rautenbach's bounded-deviation conjecture for colour-balanced matchings
Let be the complete graph on vertices, and let be a -edge-colouring. Call colour-balanced if every colour appears equally often, and for a perfect matching define
Pardey and Rautenbach's conjecture. For all integers and , every colour-balanced -edge-coloured admits a perfect matching satisfying .
This asks for a uniformly controlled colour imbalance in a perfect matching, extending the known bound when . The conjecture 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
Emma Hogan, Alex Scott and Dmitry Tsarev, “Colour-balanced subgraphs”, arXiv:2604.09449 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.