Acyclic Colorings of Directed Graphs

Noah Golowich

Published 2014-09-26Version 1

The acyclic chromatic number of a directed graph $D$, denoted $\chi_A(D)$, is the minimum positive integer $k$ such that there exists a decomposition of the vertices of $D$ into $k$ disjoint sets, each of which induces an acyclic subgraph. For any $m \geq 1$, we introduce a generalization of the acyclic chromatic number, namely $\chi_m(D)$, which is the minimum number of sets into which the vertices of a digraph can be partitioned so that each set is weakly $m$-degenerate. We show that for all digraphs $D$ without directed 2-cycles, $\chi_m(D) \leq \frac{4\bar{\Delta}(D)}{4m+1} + o(\bar{\Delta}(D))$. Because $\chi_1(D) = \chi_A(D)$, we obtain as a corollary that $\chi_A(D) \leq \frac{4}{5} \cdot \bar{\Delta}(D) + o(\bar{\Delta}(D))$, significantly improving a bound of Harutyunyan and Mohar.