A uniform bound on almost colour-balanced perfect matchings in colour-balanced cliques

2024/10/10 by Lawrence Hollom, Hollom, Lawrence
Computer Science · Engineering · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2410.07993

openalex publication_date 2024/10/10 · openalex created_date 2024/10/13 · openalex updated_date 2026/07/28

Abstract

An edge-colouring of a graph G is said to be colour-balanced if there are equally many edges of each available colour. We are interested in finding a colour-balanced perfect matching within a colour-balanced clique K_2nk with a palette of k colours. While it is not necessarily possible to find such a perfect matching, one can ask for a perfect matching as close to colour-balanced as possible. In particular, for a colouring c:E(K_2nk)→ [k], we seek to find a perfect matching M minimising f(M) = ∑_i=1^k||c^-1(i)∩ M|-n|. The previous best upper bound, due to Pardey and Rautenbach, was min f(M)≤ O(k√(nklog k)). We remove the n-dependence, proving the existence of a matching M with f(M)≤ 4^k2 for all k.

Related

• Almost color-balanced perfect matchings in color-balanced complete\n graphs
• Colour-bias perfect matchings in hypergraphs
• A note on colour-bias perfect matchings in hypergraphs
• On the Existence of Zero-Sum Perfect Matchings of Complete Graphs
• On small balanceable, strongly-balanceable and omnitonal graphs