ARTICLE
TITLE

An Improved Bound on the Sizes of Matchings Guaranteeing a Rainbow Matching

SUMMARY

A conjecture by Aharoni and Berger states that every family of nn matchings of size n+1n+1 in a bipartite multigraph contains a rainbow matching of size nn. In this paper we prove that matching sizes of (32+o(1))n\left(\frac 3 2 + o(1)\right) n suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best known one in case we only aim to find a rainbow matching of size n-1n-1. This improves previous results by Aharoni, Charbit and Howard, and Kotlar and Ziv.

PAGES
pp. P2.11

 Articles related

Gwenaël Joret, Piotr Micek    



Natalie Behague, Robert Johnson    

An automaton is synchronizing if there is a word that maps all states onto the same state. Cerný's conjecture on the length of the shortest such word is probably the most famous open problem in automata theory. We consider the closely related question of... see more


Dhruv Rohatgi, John C. Urschel, Jake Wellens    

For a graph GG, let cp(G)cp(G) denote the minimum number of cliques of GG needed to cover the edges of GG exactly once. Similarly, let bpk(G)bp_k(G) denote the minimum number of bicliques (i.e. complete bipartite subgraphs of GG) needed to cover each edg... see more


Tatiana Baginová Jajcayová, Slobodan Filipovski, Robert Jajcay    



On-Hei S. Lo, Jens M. Schmidt, Nico Van Cleemput, Carol T. Zamfirescu    

Grünbaum and Malkevitch proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most 76/77. Recently, this was improved to 359/366 (< 52/53) and the question was raised whether this can be strengthened to 41/42, ... see more