Journal article

### Rainbow matchings in properly-coloured multigraphs

Abstract:
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.
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's Version

### Access Document

Files:
• (pdf, 146.6KB)
Publisher copy:
10.1137/17M1151742

### Authors

More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
Oxford college:
Mansfield College
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
Role:
Author
Publisher:
Society for Industrial and Applied Mathematics Publisher's website
Journal:
SIAM Journal on Discrete Mathematics Journal website
Volume:
32
Issue:
3
Pages:
1577-1584
Publication date:
2018-07-10
Acceptance date:
2018-05-23
DOI:
EISSN:
1095-7146
ISSN:
0895-4801
Pubs id:
pubs:735439
URN:
UUID:
Local pid:
pubs:735439
Keywords: