{
  "id": "2410.06899",
  "version": "v1",
  "published": "2024-10-09T14:00:04.000Z",
  "updated": "2024-10-09T14:00:04.000Z",
  "title": "Cut covers of acyclic digraphs",
  "authors": [
    "Maximilian Krone"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A cut in a digraph $D=(V,A)$ is a set of arcs $\\{uv \\in A: u\\in U, v\\notin U\\}$, for some $U\\subseteq V$. It is known that the arc set $A$ is covered by $k$ cuts if and only if it admits a $k$-coloring such that no two consecutive arcs $uv, vw$ receive the same color. Alon, Bollob\\'as, Gy\\'arf\\'as, Lehel and Scott (2007) observed that every acyclic digraph of maximum indegree at most $\\binom{k}{\\lfloor k/2 \\rfloor}-1$ is covered by $k$ cuts. We prove that this degree condition is best possible (if an enormous outdegree is allowed). Notably, for $k\\geq 5$, powers of directed paths do not suffice as extremal examples. Instead, we locate the maximum $d$ such that the $d$-th power of an arbitrarily long directed path is covered by $k$ cuts between $(1-o(1)) \\frac{1}{e} 2^k$ and $\\frac{1}{2}2^k-2$. Let $k\\geq 3$ and $D$ be an acyclic digraph that is not covered by $k$ cuts. We prove that the decision problem whether a digraph that admits a homomorphism to $D$ is covered by $k$ cuts is NP-complete. If $k=3$ and $D$ is the third power of the directed path on 12 vertices, then even the restriction to planar digraphs of maximum indegree and outdegree $3$ holds.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-10-09T14:00:04.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C15"
    ],
    "keywords": [
      "acyclic digraph",
      "cut covers",
      "maximum indegree",
      "extremal examples",
      "th power"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}