Publication Date:
2018
Journal:
SIAM JOURNAL ON DISCRETE MATHEMATICS
Last Updated:
2019-07-17T11:24:45.103+01:00
Issue:
3
Volume:
32
DOI:
10.1137/17M1151742
page:
1577-1584
abstract:
© 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.
Symplectic id:
735439
Download URL:
Submitted to ORA:
Submitted
Publication Type:
Journal Article