Acyclic Colorings and Subgraphs of Directed Graphs
Noah Golowich, David Rolnick, Jacob Fox, Pavel I. Etingof · 2014
The acyclic chromatic number of a directed graph D, denoted χ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. We show that for all digraphs D without directed 2-cycles, we have χA(D) ≤ 4 5 · ∆(D) + o(∆(D)), where ∆(D) denotes the maximum arithmetic mean of the out-degree and the in-degree of a vertex in D. This result significantly improves a bound of Mohar and Harutyunyan. A related question to finding χA(D) is to find the maximum size of an acyclic induced subgraph of D. We partially resolve a conjecture of Harutyunyan that all planar digraphs on n vertices have an acyclic induced subgraph of size 3n/5. We also improve several existing lower bounds on the size of an acyclic induced subgraph for general digraphs.