The constant-deviation conjecture for colour-balanced perfect matchings
The constant-deviation conjecture for colour-balanced perfect 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
Constant-deviation conjecture. There exists an absolute constant such that for all positive integers and , every colour-balanced -edge-colouring of admits a perfect matching satisfying .
This conjecture proposes that the colour imbalance can be bounded independently of both the number of colours and the matching size. The source presents it as an open problem, contrasting it with an upper bound and a constant lower bound for matchings in complete graphs.
Sources & referencesView supporting material
Primary source
Emma Hogan, Alex Scott and Dmitry Tsarev, “Colour-balanced subgraphs”, arXiv:2604.09449 (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.