Hardness and Approximation for Coloring Digraphs

Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer +2

The dichromatic number $\vec{\ddot{I}}‡(D)$ of a digraph is the minimum number $k$ such that $V(D)$ can be partitioned into $k$ subsets, each inducing an acyclic digraph. The acyclic number…