SIAM JOURNAL ON DISCRETE MATHEMATICS
© 2018 Society for Industrial and Applied Mathematics. Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-colored by n colors with at least n + 1 edges of each color there must be a matching that uses each color 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-colored by n colors with at least n+o(n) edges of each color there must be a matching of size n−O(1) that uses each color at most once.
Submitted to ORA: