The m-Degenerate Chromatic Number of a Digraph

The digraph chromatic number of a directed graph $D$, denoted ${\chi }_A(D)$, is the minimum positive integer $k$ such that there exists a partition of the vertices of $D$ into $k$ disjoint sets, each of which induces an acyclic subgraph. For any $m\ge 1$, a digraph is weakly $m$-degenerate if each of its induced subgraphs has a vertex of in-degree or out-degree less than $m$. We introduce a generalization of the digraph chromatic number, namely ${\chi }_m(D)$, which is the minimum number of sets into which the vertices of a digraph $D$ can be partitioned so that each set induces a weakly $m$-degenerate subgraph. We show that for all digraphs $D$ without directed 2-cycles, $\chi_m(D) \leq \frac{2{\Delta}(D)}{4m+1} + O(1)$\mathrm{.}Because$\chi_1(D) = \chi_A(D)$, we obtain as a corollary that ${\chi }_A(D)\le 2\mathrm{/}5\cdot \mathrm{\Delta }(D)+O(1)$. We then use this bound to show that $\chi_A(D) \leq \sqrt{2/3} \cdot \tilde{\Delta}(D) + O(1)$, substantially improving a bound of Harutyunyan and Mohar that states that ${\chi }_A(D)\le (1-e^{-13})\cdot \tilde{\mathrm{\Delta }}(D)$ for large enough $\tilde{\mathrm{\Delta }}(D)$.