{
  "id": "1305.1466",
  "version": "v2",
  "published": "2013-05-07T11:07:42.000Z",
  "updated": "2013-10-21T16:26:05.000Z",
  "title": "Large matchings in bipartite graphs have a rainbow matching",
  "authors": [
    "Daniel Kotlar",
    "Ran Ziv"
  ],
  "journal": "European Journal of Combinatorics. Vol. 38, 97-101 (2013)",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $g(n)$ be the least number such that every collection of $n$ matchings, each of size at least $g(n)$, in a bipartite graph, has a full rainbow matching. Aharoni and Berger \\cite{AhBer} conjectured that $g(n)=n+1$ for every $n>1$. This generalizes famous conjectures of Ryser, Brualdi and Stein. Recently, Aharoni, Charbit and Howard \\cite{ACH} proved that $g(n)\\le\\lfloor\\frac{7}{4}n\\rfloor$. We prove that $g(n)\\le\\lfloor\\frac{5}{3} n\\rfloor$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-10-21T16:26:05.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bipartite graph",
      "large matchings",
      "generalizes famous conjectures",
      "collection",
      "full rainbow matching"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1305.1466K"
    }
  }
}