Journal article icon

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

Actions


Access Document


Files:
Publisher copy:
10.1137/17M1151742

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
Oxford college:
Mansfield College
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
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:
uri:5f8085e8-bad7-4206-82da-9b80b5a39ef7
UUID:
uuid:5f8085e8-bad7-4206-82da-9b80b5a39ef7
Local pid:
pubs:735439

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP