Daniel Kotlar, Ziv Ran
Abstract
Abstract. A recent conjecture of Aharoni, Charbit and Howard states that n matchings, each of size n+ 1, in a bipartite graph have a rainbow matching of size n. The same authors proved that if the size of the matchings is b 7 4 nc then a rainbow matching of size n exists. In this work we apply a different method to improve the bound to b 5 3 nc. 1.
A significance statement is not available in the OpenAlex record.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
Abstract. A recent conjecture of Aharoni, Charbit and Howard states that n matchings, each of size n+ 1, in a bipartite graph have a rainbow matching of size n. The same authors proved that if the size of the matchings is b 7 4 nc then a rainbow matching of size n exists. In this work we apply a different method to improve the bound to b 5 3 nc. 1.
Key concepts: Rainbow, Bipartite graph, Combinatorics, Matching (statistics), Conjecture, Mathematics, Graph, Upper and lower bounds