2017/10/09 by Keevash, Peter, Yepremyan, Liana
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1710.03041
Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-coloured by n colours with at least n + 1 edges of each colour there must be a matching that uses each colour exactly once. In this paper we consider the same question without the bipartiteness assumption. We show that in any multigraph with edge multiplicities o(n) that is properly edge-coloured by n colours with at least n + o(n) edges of each colour there must be a matching of size n-O(1) that uses each colour at most once.