{
  "id": "2203.12470",
  "version": "v1",
  "published": "2022-03-23T15:05:58.000Z",
  "updated": "2022-03-23T15:05:58.000Z",
  "title": "On Factors with Prescribed Degrees in Bipartite Graphs",
  "authors": [
    "Amin Bahmanian"
  ],
  "comment": "3 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We establish a new criterion for a bigraph to have a subgraph with prescribed degree conditions. We show that the bigraph $G[X,Y]$ has a spanning subgraph $F$ such that $g(x)\\leq deg_F(x) \\leq f(x)$ for $x\\in X$ and $deg_F(y) \\leq f(y)$ for $y\\in Y$ if and only if $\\sum\\nolimits_{b\\in B} f(b)\\geq \\sum\\nolimits_{a\\in A} \\max \\big\\{0, g(a) - deg_{G-B}(a)\\big\\}$ for $A\\subseteq X, B\\subseteq Y$. Using Folkman-Fulkerson's Theorem, Cymer and Kano found a different criterion for the existence of such a subgraph (Graphs Combin. 32 (2016), 2315--2322). Our proof is self-contained and relies on alternating path technique. As an application, we prove the following extension of Hall's theorem. A bigraph $G[X,Y]$ in which each edge has multiplcity at least $m$ has a subgraph $F$ with $g(x)\\leq deg_F(x)\\leq f(x)\\leq deg(x)$ for $x\\in X$, $deg_F(y)\\leq m$ for $y\\in Y$ if and only if $\\sum_{y\\in N_G(S)}f(y)\\geq \\sum_{x\\in S}g(x)$ for $S\\subseteq X$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-03-23T15:05:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70"
    ],
    "keywords": [
      "bipartite graphs",
      "prescribed degree conditions",
      "folkman-fulkersons theorem",
      "graphs combin",
      "alternating path technique"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 3,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}