Rainbow matchings in bipartite multigraphs
Suppose that k is a non-negative integer and a bipartite multigraph G is the union of N = k + 2 k + 1 n - ( k + 1 ) matchings M 1 , ⋯ , M N , each of size n . We show that G has a rainbow matching of size n - k , i.e. a matching of size n - k with all edges coming from different M i ’s. Several choi...
Saved in:
Published in: | Periodica mathematica Hungarica 2017-03, Vol.74 (1), p.108-111 |
---|---|
Main Authors: | , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | Suppose that
k
is a non-negative integer and a bipartite multigraph
G
is the union of
N
=
k
+
2
k
+
1
n
-
(
k
+
1
)
matchings
M
1
,
⋯
,
M
N
, each of size
n
. We show that
G
has a rainbow matching of size
n
-
k
, i.e. a matching of size
n
-
k
with all edges coming from different
M
i
’s. Several choices of the parameter
k
relate to known results and conjectures. |
---|---|
ISSN: | 0031-5303 1588-2829 |
DOI: | 10.1007/s10998-016-0172-x |