Abstract:A $k$-edge-coloured graph is colour-balanced if each colour appears equally often. Resolving a conjecture of Pardey and Rautenbach, we show that any colour-balanced $k$-edge-coloured complete graph $K_{2kt}$ contains a perfect matching that can be made colour-balanced by recolouring $O(k^2)$ edges. More generally, we obtain analogous bounds for arbitrary bounded-degree spanning subgraphs of edge-coloured complete graphs and for perfect matchings in edge-coloured $r$-uniform complete hypergraphs in a more general vector-label setting. The former result answers a question recently posed by Banerjee and Hollom, and significantly improves earlier bounds for all previously studied classes of subgraph. Our proofs reduce each of these problems to a setting in which we can apply a bound for perfect matchings in the complete bipartite graph, established via a linear relaxation and a necklace-splitting argument.
From: Emma Hogan [view email]
[v1]
Fri, 10 Apr 2026 16:07:10 UTC (33 KB)
[v2]
Sat, 11 Jul 2026 20:14:26 UTC (33 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。