{
  "id": "2401.05205",
  "version": "v1",
  "published": "2024-01-10T15:04:02.000Z",
  "updated": "2024-01-10T15:04:02.000Z",
  "title": "Long antipaths and anticycles in oriented graphs",
  "authors": [
    "Bin Chen",
    "Xinmin Hou",
    "Hongyu Zhou"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\delta^{0}(D)$ be the minimum semi-degree of an oriented graph $D$. Jackson (1981) proved that every oriented graph $D$ with $\\delta^{0}(D)\\geq k$ contains a directed path of length $2k$ when $|V(D)|>2k+2$, and a directed Hamilton cycle when $|V(D)|\\le 2k+2$. Stein~(2020) further conjectured that every oriented graph $D$ with $\\delta^{0}(D)>k/2$ contains any orientated path of length $k$. Recently, Klimo\\u{s}ov\\'{a} and Stein (DM, 2023) introduced the minimum pseudo-semi-degree $\\tilde\\delta^0(D)$ (a slight weaker than the minimum semi-degree condition as $\\tilde\\delta^0(D)\\ge \\delta^0(D))$ and showed that every oriented graph $D$ with $\\tilde\\delta^{0}(D)\\ge (3k-2)/4$ contains each antipath of length $k$ for $k\\geq 3$. In this paper, we improve the result of Klimo\\u{s}ov\\'{a} and Stein by showing that for all $k\\geq 2$, every oriented graph with $\\tilde\\delta^0(D)\\ge(2k+1)/3$ contains either an antipath of length at least $k+1$ or an anticycle of length at least $k+1$. Furthermore, we answer a problem raised by Klimo\\u{s}ov\\'{a} and Stein in the negative.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-01-10T15:04:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C38"
    ],
    "keywords": [
      "oriented graph",
      "long antipaths",
      "minimum semi-degree condition",
      "minimum pseudo-semi-degree",
      "slight weaker"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}