Pardey and Rautenbach's bounded-deviation conjecture for colour-balanced matchings

Less than 1 year old · traced to

Let K2ktK_{2kt} be the complete graph on 2kt2kt vertices, and let c ⁣:E(K2kt)→[k]c\colon E(K_{2kt})\to [k] be a kk-edge-colouring. Call cc colour-balanced if every colour appears equally often, and for a perfect matching MM define

fc(M)=∑i=1k∣∣c−1(i)∩M∣−t∣.f_c(M)=\sum_{i=1}^k\left|\left|c^{-1}(i)\cap M\right|-t\right|.

Pardey and Rautenbach's conjecture. For all integers k≥2k\geq 2 and t≥1t\geq 1, every colour-balanced kk-edge-coloured K2ktK_{2kt} admits a perfect matching MM satisfying fc(M)=O(k2)f_c(M)=O(k^2).

This asks for a uniformly controlled colour imbalance in a perfect matching, extending the known bound fc(M)≤2f_c(M)\leq 2 when k=3k=3. The conjecture remains open in the supplied source.

References

Primary source

Emma Hogan, Alex Scott and Dmitry Tsarev, “Colour-balanced subgraphs”, arXiv:2604.09449 (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.