Rainbow matchings in properly-coloured multigraphs

10/09/2017
by   Peter Keevash, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset