Rainbow matchings in bipartite multigraphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Rainbow matchings in bipartite multigraphs

Authors:	János Barát András Gyárfás Gábor N. Sárközy

Affiliation:	1.MTA-ELTE Geometric and Algebraic Combinatorics Research Group,Budapest,Hungary;2.Alfréd Rényi Institute of Mathematics,Hungarian Academy of Sciences,Budapest,Hungary;3.Computer Science Department,Worcester Polytechnic Institute,Worcester,USA

Abstract:	Suppose that k is a non-negative integer and a bipartite multigraph G is the union of $$begin{aligned} N=leftlfloor frac{k+2}{k+1}nrightrfloor -(k+1) end{aligned}$$ matchings (M_1,dots ,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.

Keywords:
本文献已被 SpringerLink 等数据库收录！