The mm-degenerate chromatic number of a digraph

The digraph chromatic number   of a directed graph DD, denoted χA(D)χA(D), is the minimum positive integer kk such that there exists a partition of the vertices of DD into kk disjoint sets, each of which induces an acyclic subgraph. For any m≥1m≥1, a digraph is weakly  mm-degenerate   if each of its induced subgraphs has a vertex of in-degree or out-degree less than mm. We introduce a generalization of the digraph chromatic number, namely χm(D)χm(D), which is the minimum number of sets into which the vertices of a digraph DD can be partitioned so that each set induces a weakly mm-degenerate subgraph. We show that for all digraphs DD without directed 2-cycles, χm(D)≤2Δ(D)4m+1+O(1). Because χ1(D)=χA(D)χ1(D)=χA(D), we obtain as a corollary that χA(D)≤2/5⋅Δ(D)+O(1)χA(D)≤2/5⋅Δ(D)+O(1). We then use this bound to show that χA(D)≤2/3⋅Δ̃(D)+O(1), substantially improving a bound of Harutyunyan and Mohar that states that χA(D)≤(1−e−13)⋅Δ̃(D) for large enough Δ̃(D).