{"id":"arxiv/2603.02947","url":"https://arxiv.org/abs/2603.02947","tags":["math.CO"],"score":0,"title":"Acyclic sets and colorings in digraphs under restrictions on degrees and cycle lengths","domain":"math.CO","source":"arxiv","authors":["Ararat Harutyunyan","Colin McDiarmid","Gil Puig i Surroca"],"reviews":0,"subject":"math.CO","summary":"Given a digraph $D$, we denote by $\\vecα(D)$ the maximum size of an acyclic set of $D$ (i.e. a set of vertices which induces a subdigraph with no directed cycles), and by $\\vecχ(D)$ the minimum number of acyclic sets into which $V(D)$ can be partitioned. In this paper, we study $\\vecα(D)$ and $\\vecχ(D)$ from various perspectives, including restrictions on degrees and cycle lengths. A main result is that, if $D$ is a random $r$-regular digon-free simple digraph of order $n$, then $\\vecα(D) = Θ(n \\log r /r)$ with high probability. This corresponds to a result of Spencer and Subramanian on the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-03","reactions":{}}