{
  "id": "2408.16733",
  "version": "v1",
  "published": "2024-08-29T17:25:58.000Z",
  "updated": "2024-08-29T17:25:58.000Z",
  "title": "Erdős-Pósa property of tripods in directed graphs",
  "authors": [
    "Marcin Briański",
    "Meike Hatzel",
    "Karolina Okrasa",
    "Michał Pilipczuk"
  ],
  "comment": "12 pages, 4 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $D$ be a directed graphs with distinguished sets of sources $S\\subseteq V(D)$ and sinks $T\\subseteq V(D)$. A tripod in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix. We prove that tripods in directed graphs exhibit the Erd\\H{o}s-P\\'osa property. More precisely, there is a function $f\\colon \\mathbb{N}\\to \\mathbb{N}$ such that for every digraph $D$ with sources $S$ and sinks $T$, if $D$ does not contain $k$ vertex-disjoint tripods, then there is a set of at most $f(k)$ vertices that meets all the tripods in $D$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-29T17:25:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "directed graphs",
      "erdős-pósa property",
      "distinct start-vertices",
      "disjoint apart",
      "vertex-disjoint tripods"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}