Digraph Coloring and Distance to Acyclicity

Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos

In $k$-Digraph Coloring we are given a digraph and are asked to partition its vertices into at most $k$ sets, so that each set induces a DAG. This well-known problem is NP-hard, as…