2024/10/09 by Maximilian Krone, Krone, Maximilian
Computer Science · Engineering · Mathematics · #05C15 #05C20 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2410.06899
openalex publication_date 2024/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A cut in a digraph D=(V,A) is a set of arcs \uv ∈ A: u∈ U, v∉ U\, for some U⊆ 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 \binomk\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≥ 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)) (1)/(e) 2k and (1)/(2)2k-2. Let k≥ 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.