Cut covers of acyclic digraphs
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929533822697472 |
|---|---|
| author | Krone, Maximilian |
| author_facet | Krone, Maximilian |
| contents | 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ás, Gyárfás, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06899 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cut covers of acyclic digraphs Krone, Maximilian Combinatorics 05C20, 05C15 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ás, Gyárfás, 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. |
| title | Cut covers of acyclic digraphs |
| topic | Combinatorics 05C20, 05C15 |
| url | https://arxiv.org/abs/2410.06899 |