{"id":"arxiv/2604.09449","url":"https://arxiv.org/abs/2604.09449","tags":["math.CO"],"score":0,"title":"Colour-balanced subgraphs","domain":"math.CO","source":"arxiv","authors":["Emma Hogan","Alex Scott","Dmitry Tsarev"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-10","reactions":{}}