{
  "id": "1707.03600",
  "version": "v1",
  "published": "2017-07-12T08:53:06.000Z",
  "updated": "2017-07-12T08:53:06.000Z",
  "title": "On splitting digraphs",
  "authors": [
    "Donglei Yang",
    "Yandong Bai",
    "Guanghui Wang",
    "Jianliang Wu"
  ],
  "comment": "8 pages, 0 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1995, Stiebitz asked the following question: For any positive integers $s,t$, is there a finite integer $f(s,t)$ such that every digraph $D$ with minimum out-degree at least $f(s,t)$ admits a bipartition $(A, B)$ such that $A$ induces a subdigraph with minimum out-degree at least $s$ and $B$ induces a subdigraph with minimum out-degree at least $t$? We give an affirmative answer for tournaments, bipartite tournaments, multipartite tournaments, and digraphs with bounded maximum in-degrees. In particular, we show that for every $0<\\epsilon<\\frac{1}{4}$, there exists an integer $\\delta_0$ such that every tournament with minimum out-degree at least $\\delta_0$ admits a bisection $(A, B)$, so that each vertex has at least $(\\frac{1}{4}-\\epsilon)$ of its out-neighbors in $A$, and in $B$ as well.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-07-12T08:53:06.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "minimum out-degree",
      "splitting digraphs",
      "subdigraph",
      "bounded maximum in-degrees",
      "multipartite tournaments"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}