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...

Full description

Saved in:
Bibliographic Details
Published in:Periodica mathematica Hungarica 2017-03, Vol.74 (1), p.108-111
Main Authors: Barát, János, Gyárfás, András, Sárközy, Gábor N.
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!
Description
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