Colour-balanced subgraphs

Emma Hogan Alex Scott Dmitry Tsarev · 2026

Read Colour-balanced subgraphs by Emma Hogan Alex Scott Dmitry Tsarev (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-09449.txt.

Introduction

Hogan, Scott, and Tsarev study colour-balanced subgraphs, resolving a conjecture of Pardey and Rautenbach. A graph with k edge colours counts as colour-balanced when each colour shows up equally often. The authors show every colour-balanced K-2kt graph with k edge colours holds a perfect matching made colour-balanced by recolouring O of k squared edges. More generally, analogous bounds cover bounded-degree spanning subgraphs and perfect matchings in r-uniform hypergraphs. Proofs reduce each problem to a bipartite matching bound via linear relaxation and necklace-splitting.

Catalog record

CREATOREmma Hogan Alex Scott Dmitry Tsarev
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89005
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.09449

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Colour-balanced subgraphs Emma Hogan Alex Scott Dmitry Tsarev Abstract A k 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 k -edge-coloured complete graph K 2 ​ k ​ t K_{2kt} contains a perfect matching that can be made colour-balanced by recolouring O ⁡ ( k 2 ) 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 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. 1 Introduction A recurring theme in extremal combinatorics is the problem of identifying substructures that are, in some sense, representative of a larger combinatorial object. In graph theory, one formulation of this problem is as follows: given an edge-labelled graph, can one find a subgraph of a prescribed type whose label distribution is close to that of the host graph? Questions of this type have been studied in the context of k -edge-coloured complete graphs for a range of substructures, including perfect matchings ( [ 5 , 10 , 14 , 13 , 19 ] ), spanning forests ( [ 5 , 12 , 16 , 20 ] ), and factors ( [ 3 ] ), with various bounds obtained on how closely such a subgraph can reflect the global distribution of colours; however, many natural problems remain open. The aim of this paper is to improve known bounds on a range of such problems. Problems on representative subgraphs have their roots in zero-sum Ramsey theory. The underlying question in this field is to find a copy of a fixed subgraph H in a labelled clique K_{n} such that the sum of the edge labels over the copy of H is zero. When K_{n} is labelled by colours \{-1,1\} , a zero-sum subgraph corresponds to a subgraph with an equal number of edges of each colour, and is therefore representative of a host graph with an equal number of edges of each colour. Variants of the problem where E(K_{n}) is labelled by some finite abelian group have also received considerable attention. For a survey of early developments on zero-sum graph problems, see [ 6 ] . Inspired by early work of Bialostocki and Dierker [ 4 ] on zero-sum matchings, Caro, Hansberg, Lauri and Zarb [ 5 ] asked whether it was always possible to find a zero-sum perfect matching in a zero-sum complete graph K_{4n} with edges labelled by \{-1,1\} . The question was answered affirmatively by Ehard, Mohr and Rautenbach [ 10 ] and independently by Kittipassorn and Sinsap [ 14 ] . Kittipassorn and Sinsap further initiated the study of so-called colour-balanced subgraphs with more than 2 colours. Let G be a graph and let c\colon E(G)\to[k] be a k -edge-colouring of G . We call both G and c colour-balanced if \lvert c^{-1}(i)\rvert=\lvert c^{-1}(j)\rvert for each i,j\in[k] . Motivated by the work of Caro, Hansberg, Lauri and Zarb, Kittipassorn and Sinsap [ 14 ] asked whether, for any positive integer t , every colour-balanced k -edge-colouring of the complete graph K_{2kt} admits a colour-balanced perfect matching M . This question was answered negatively by Pardey and Rautenbach [ 19 ] , who found an example of a 3 -edge-coloured K_{6} admitting no colour-balanced perfect matching. Instead, they asked for a bound on the colour imbalance of an optimal perfect matching. Define f_{c}(M)=\sum_{i=1}^{k}\lvert\lvert c^{-1}(i)\cap M\rvert-t\rvert to be the total deviation from being colour-balanced across all colour classes, noting that in a colour-balanced perfect matching of K_{2kt} , every colour appears exactly t times. Pardey and Rautenbach proved that, when k=3 , there exists a perfect matching M of K_{6t} satisfying f_{c}(M)\leq 2 , and for general k they conjectured the following. Conjecture 1.1 (Conjecture 1, [ 19 ] ) . For all integers k\geq 2 and t\geq 1 , every colour-balanced k -edge-coloured K_{2kt} admits a perfect matching M satisfying f_{c}(M)=O(k^{2}) . Making progress towards this conjecture, they found that every colour-balanced k -edge-colouring of K_{2kt} admits a perfect matching M satisfying f_{c}(M)\leq 3k\sqrt{kt\log 2k} . Further recent progress by Hollom [ 13 ] removed the dependence on t from this bound, establishing the existence of a perfect matching M satisfying f_{c}(M)\leq 4^{k^{2}} . In the following result, we let n=kt for simplicity. Our first result improves on the bound of Hollom and resolves the conjecture of Pardey and Rautenbach. Theorem 1.2 . Let c be a colour-balanced k -edge-colouring of K_{2n} . Then there exists a perfect matching M of K_{2n} satisfying f_{c}(M)=O(k^{2}). In fact, our proof techniques allow us to obtain much stronger results for representative subgraphs in the context of vector-labelled graphs. For a graph G , a subgraph G^{\prime} of G , and a function h\colon E(G)\to\mathbb{R}^{k} assigning vectors to the edges of G , we denote by h(G^{\prime}) the sum \sum_{e\in E(G^{\prime})}h(e) . We say that G^{\prime} is representative of G if h(G^{\prime})/e(G^{\prime}) is equal to h(G)/e(G) . Analogously to the definition of f_{c} , we define f_{h}(G^{\prime})=\left\|h(G^{\prime})-\frac{e(G^{\prime})}{e(G)}h(G)\right\|_{1}. Thus f_{h} measures how far from representative a subgraph G^{\prime} of G is. Note that by translating each vector by a constant amount so that h(G)=0 , we may equivalently view the problem of finding a representative subgraph as a problem in zero-sum Ramsey theory over \mathbb{R}^{k} . The following theorem shows that, under mild assumptions on h , complete graphs admit almost representative perfect matchings. Theorem 1.3 . Let h\colon E(K_{2n})\to\mathbb{R}^{k} such that \left\lVert h(e)\right\rVert_{1}\leq 1 for all e\in E(K_{2n}) . Then there is a perfect matching M of K_{2n} satisfying f_{h}(M)=O(k^{2}). To see that this is indeed a more general setting than the edge-colouring problem, let b_{1},\dotsc,b_{k} denote the standard basis of \mathbb{R}^{k} . Given a k -edge-coloured graph G , let h assign each edge e of colour i the vector b_{i} . Then when G is colour-balanced, a perfect matching M of G satisfies f_{h}(M)=f_{c}(M) , and in general, a subgraph is representative exactly when it contains the expected proportion of the edges in each colour class. Furthermore, when G is not colour-balanced, our theorem gives the same quadratic error bound for representative perfect matchings of graphs with unbalanced colour-counts. Various authors have also considered bounds for other colour-balanced subgraphs. Hollom [ 13 ] asked whether, for an r -vertex graph F , it is always possible to find an F -factor H in a colour-balanced K_{n} such that f_{c}(H) is bounded by a function of only H and k . This question was answered affirmatively by Banerjee and Hollom [ 3 ] , who obtained a bound of f_{c}(H)\leq(8rk)^{(8rk)^{k}} . When k=2 , there has also been considerable research on embedding spanning forests. For any fixed spanning forest F , it is known that f_{c}(F) is always bounded by an error that is linear

Read the complete text